{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 203,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "%matplotlib inline\n",
    "from scilab import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 204,
   "metadata": {},
   "outputs": [],
   "source": [
    "import random  \n",
    "import numpy as np  \n",
    "from matplotlib import pyplot as plt  \n",
    "\n",
    "def mazeGen_BrkCir(num_rows=20, num_cols=20):  \n",
    "    \n",
    "    LEFT, UP, RIGHT, DOWN = 0,1,2,3\n",
    "    M = np.ones((num_rows,num_cols,4), dtype=np.uint8)\n",
    "    M[0,:,UP] = 0\n",
    "    M[-1,:,DOWN] = 0\n",
    "    M[:,0,LEFT] = 0\n",
    "    M[:,-1,RIGHT] = 0\n",
    "\n",
    "    class maze_graph_rec:\n",
    "        def __init__(self, matrix):\n",
    "            self.M = matrix\n",
    "            num_rows,num_cols = matrix.shape[:2]\n",
    "            self.vertices = [array((r,c)) for r in range(num_rows) for c in range(num_cols)]\n",
    "\n",
    "        def edgesOf(self, v):\n",
    "            neis = self.M[(*v,)]\n",
    "            deltas = np.array([[0,-1],[-1,0],[0,1],[1,0]])\n",
    "\n",
    "            return [v + d for d in deltas[neis==1]]\n",
    "\n",
    "        def remove_edge(self, v1, v2):\n",
    "            delta = (*(v2 - v1),)\n",
    "            memmap = {(0,-1):0,(-1,0):1,(0,1):2,(1,0):3}\n",
    "            ind = memmap[delta]\n",
    "            self.M[(*v1,)][ind] = 0\n",
    "\n",
    "            delta = (*(v1 - v2),)\n",
    "            ind = memmap[delta]\n",
    "            self.M[(*v2,)][ind] = 0\n",
    "\n",
    "        @property\n",
    "        def edges(self):\n",
    "            def half_edges(v):\n",
    "                neis = self.M[(*v,)][:2]\n",
    "                deltas = np.array([[0,-1],[-1,0]])\n",
    "                return [v + d for d in deltas[neis==1]]\n",
    "            edges = [(v,n) for v in self.vertices for n in half_edges(v)]\n",
    "            return edges\n",
    "\n",
    "    G = maze_graph_rec(M)\n",
    "    edges_in_circle = [(tuple(v1),tuple(v2)) for v1,v2 in G.edges]\n",
    "\n",
    "    M_temp = M.copy()\n",
    "    G_temp = maze_graph_rec(M_temp)\n",
    "\n",
    "    def check_in_circle(v, G):\n",
    "        neis = G.edgesOf(v)\n",
    "        tv = tuple(v)\n",
    "        if len(neis) == 1:\n",
    "            tnei = tuple(neis[0])\n",
    "            print(tv, \"has one nei \", tnei)\n",
    "            sucess = False\n",
    "            try:\n",
    "                edges_in_circle.remove((tv, tnei))\n",
    "                sucess = True\n",
    "            except:pass\n",
    "            try:\n",
    "                edges_in_circle.remove((tnei,tv))\n",
    "                sucess = True\n",
    "            except:pass\n",
    "            \n",
    "            assert(sucess)\n",
    "\n",
    "            G.remove_edge(v, neis[0])\n",
    "            print(len(G.edges), \"edges in circle(graph)\")\n",
    "            print(len(edges_in_circle), \"edges in circle(list)\")\n",
    "            check_in_circle(neis[0], G)\n",
    "\n",
    "    while edges_in_circle:\n",
    "        print(\"\\n\",len(edges_in_circle), \"edges\")\n",
    "        ie = random.randint(0, len(edges_in_circle)-1)\n",
    "\n",
    "        tv1, tv2 = edges_in_circle.pop(ie)\n",
    "        print(\"choice edge: \",tv1,tv2)\n",
    "        v1 = array(tv1)\n",
    "        v2 = array(tv2)\n",
    "        G.remove_edge(v1,v2)\n",
    "        G_temp.remove_edge(v1,v2)\n",
    "\n",
    "        check_in_circle(v1, G_temp)\n",
    "        check_in_circle(v2, G_temp)\n",
    "\n",
    "    M[0,0,0] = 1  \n",
    "    M[num_rows-1,num_cols-1,2] = 1  \n",
    "\n",
    "    # Generate the image for display  \n",
    "    image = np.zeros((num_rows*10,num_cols*10), dtype=np.uint8)\n",
    "    for row in range(0,num_rows):  \n",
    "        for col in range(0,num_cols):  \n",
    "            cell_data = M[row,col]  \n",
    "            for i in range(10*row+2,10*row+8):  \n",
    "                image[i,range(10*col+2,10*col+8)] = 255  \n",
    "            if cell_data[0] == 1:   \n",
    "                image[range(10*row+2,10*row+8),10*col] = 255  \n",
    "                image[range(10*row+2,10*row+8),10*col+1] = 255  \n",
    "            if cell_data[1] == 1:   \n",
    "                image[10*row,range(10*col+2,10*col+8)] = 255  \n",
    "                image[10*row+1,range(10*col+2,10*col+8)] = 255  \n",
    "            if cell_data[2] == 1:   \n",
    "                image[range(10*row+2,10*row+8),10*col+9] = 255  \n",
    "                image[range(10*row+2,10*row+8),10*col+8] = 255  \n",
    "            if cell_data[3] == 1:   \n",
    "                image[10*row+9,range(10*col+2,10*col+8)] = 255  \n",
    "                image[10*row+8,range(10*col+2,10*col+8)] = 255  \n",
    "\n",
    "    import matplotlib.cm as cm  \n",
    "    # Display the image  \n",
    "    plt.imshow(image, cmap = cm.Greys_r, interpolation='none')  \n",
    "    plt.show()\n",
    "    \n",
    "    return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 205,
   "metadata": {
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      " 40 edges\n",
      "choice edge:  (0, 4) (0, 3)\n",
      "(0, 4) has one nei  (1, 4)\n",
      "38 edges in circle(graph)\n",
      "38 edges in circle(list)\n",
      "\n",
      " 38 edges\n",
      "choice edge:  (4, 4) (4, 3)\n",
      "(4, 4) has one nei  (3, 4)\n",
      "36 edges in circle(graph)\n",
      "36 edges in circle(list)\n",
      "\n",
      " 36 edges\n",
      "choice edge:  (2, 1) (2, 0)\n",
      "\n",
      " 35 edges\n",
      "choice edge:  (2, 3) (1, 3)\n",
      "\n",
      " 34 edges\n",
      "choice edge:  (1, 0) (0, 0)\n",
      "(0, 0) has one nei  (0, 1)\n",
      "32 edges in circle(graph)\n",
      "32 edges in circle(list)\n",
      "\n",
      " 32 edges\n",
      "choice edge:  (4, 0) (3, 0)\n",
      "(4, 0) has one nei  (4, 1)\n",
      "30 edges in circle(graph)\n",
      "30 edges in circle(list)\n",
      "\n",
      " 30 edges\n",
      "choice edge:  (4, 3) (3, 3)\n",
      "(4, 3) has one nei  (4, 2)\n",
      "28 edges in circle(graph)\n",
      "28 edges in circle(list)\n",
      "\n",
      " 28 edges\n",
      "choice edge:  (1, 4) (1, 3)\n",
      "(1, 4) has one nei  (2, 4)\n",
      "26 edges in circle(graph)\n",
      "26 edges in circle(list)\n",
      "\n",
      " 26 edges\n",
      "choice edge:  (3, 2) (3, 1)\n",
      "\n",
      " 25 edges\n",
      "choice edge:  (3, 1) (2, 1)\n",
      "\n",
      " 24 edges\n",
      "choice edge:  (4, 2) (4, 1)\n",
      "(4, 2) has one nei  (3, 2)\n",
      "22 edges in circle(graph)\n",
      "22 edges in circle(list)\n",
      "(4, 1) has one nei  (3, 1)\n",
      "21 edges in circle(graph)\n",
      "21 edges in circle(list)\n",
      "(3, 1) has one nei  (3, 0)\n",
      "20 edges in circle(graph)\n",
      "20 edges in circle(list)\n",
      "(3, 0) has one nei  (2, 0)\n",
      "19 edges in circle(graph)\n",
      "19 edges in circle(list)\n",
      "(2, 0) has one nei  (1, 0)\n",
      "18 edges in circle(graph)\n",
      "18 edges in circle(list)\n",
      "(1, 0) has one nei  (1, 1)\n",
      "17 edges in circle(graph)\n",
      "17 edges in circle(list)\n",
      "\n",
      " 17 edges\n",
      "choice edge:  (1, 2) (0, 2)\n",
      "\n",
      " 16 edges\n",
      "choice edge:  (2, 3) (2, 2)\n",
      "\n",
      " 15 edges\n",
      "choice edge:  (3, 4) (2, 4)\n",
      "(3, 4) has one nei  (3, 3)\n",
      "13 edges in circle(graph)\n",
      "13 edges in circle(list)\n",
      "(2, 4) has one nei  (2, 3)\n",
      "12 edges in circle(graph)\n",
      "12 edges in circle(list)\n",
      "(2, 3) has one nei  (3, 3)\n",
      "11 edges in circle(graph)\n",
      "11 edges in circle(list)\n",
      "(3, 3) has one nei  (3, 2)\n",
      "10 edges in circle(graph)\n",
      "10 edges in circle(list)\n",
      "(3, 2) has one nei  (2, 2)\n",
      "9 edges in circle(graph)\n",
      "9 edges in circle(list)\n",
      "\n",
      " 9 edges\n",
      "choice edge:  (0, 2) (0, 1)\n",
      "(0, 2) has one nei  (0, 3)\n",
      "7 edges in circle(graph)\n",
      "7 edges in circle(list)\n",
      "(0, 3) has one nei  (1, 3)\n",
      "6 edges in circle(graph)\n",
      "6 edges in circle(list)\n",
      "(1, 3) has one nei  (1, 2)\n",
      "5 edges in circle(graph)\n",
      "5 edges in circle(list)\n",
      "(0, 1) has one nei  (1, 1)\n",
      "4 edges in circle(graph)\n",
      "4 edges in circle(list)\n",
      "\n",
      " 4 edges\n",
      "choice edge:  (2, 2) (2, 1)\n",
      "(2, 2) has one nei  (1, 2)\n",
      "2 edges in circle(graph)\n",
      "2 edges in circle(list)\n",
      "(1, 2) has one nei  (1, 1)\n",
      "1 edges in circle(graph)\n",
      "1 edges in circle(list)\n",
      "(1, 1) has one nei  (2, 1)\n",
      "0 edges in circle(graph)\n",
      "0 edges in circle(list)\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAPkAAAD5CAYAAADlT5OQAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAACzdJREFUeJzt3V+opHUdx/H3aLspcVq6sSBEL+J8\nb86hYAMNWzsX68VGsiVBN/ZHqW42MBAqY+2qiwJbyEKUFV0NIkrTrraCsE2SCsVgFrcv1GWBSLC6\noUi7O12cGRnszJk/Z/48z9f3Cw7M88yc83z2t/OZ55lnfuc8nV6vh6S6rlh1AEmLZcml4iy5VJwl\nl4qz5FJxllwq7l2zfFNEXAE8AHwYeBP4cmb+fZ7BJM1Jr9eb+mt9ff229fX1U/3bN66vr/9qt8cD\nPaDX7XZ7g9tt+GpT3jZlbVvetmQd1b/OLJNhIuIE8JfM/Fl/+Z+Z+cFRj+90Oj22U9DpdKbe3qq0\nKW+bskK78rYla6/X2zHkrO/J3wu8OrR8KSJmOvSXtFizFvM1YG1o+YrMvDjqwd1ul42NDQBmOXJY\npTblbVNWaFfeNmV9u1lL/kfgVuDnEXEj0N3twZubm0B7DnsG2pS3TVmhXXnbknXUC9GsJX8KuCUi\nngM6wB0z/hxJCzbTibepN+KJt4VrU1ZoV962ZJ33iTdJLWHJpeKW8rHX8FuCtp2lXGXeeR0iNnXM\nV51rHuO7rH/DXrK6J5eKs+RScZZcKs6SS8VZcqk4Sy4VZ8ml4iy5VJwll4qz5FJxllwqzpJLxVly\nqThLLhVnyaXiLLlUnCWXirPkUnGWXCrOkkvFWXKpOEsuFWfJpeIsuVScJZeKW8oVVAZXf2jLheMG\nRuVd9ZU/ptXEMd/tudC28W069+RScZZcKs6SS8VZcqk4Sy4VZ8ml4iy5VNxEn5NHxA3A9zNzKyI+\nBJwCesBZ4FhmXl5cREl7MXZPHhHfAB4GruqvOgEcz8xDQAc4urh4kvZqksP1fwC3DS0fBM70b58G\nDs87lKT5GXu4nplPRsT1Q6s6mTmYd3gBODDuZ3S7XTY2NoD2TVlcZd5pt+3YLm77bcr6drPMXR9+\n/70GnB/3DZubm4Bz16c1zVhVGdvBfcsw6Xi1JeuoLLOcXX8xIrb6t48Az87wMyQtySx78ruBkxGx\nHzgHPDHfSJLmqbOMw41Op9ODOoeUTTpEG6gytoP7lqHg4fqOD3IyjFTcUv5oxCRWffZyFM+uL07b\n8raVe3KpOEsuFWfJpeIsuVScJZeKs+RScZZcKs6SS8VZcqk4Sy4VZ8ml4iy5VJwll4qz5FJxllwq\nzpJLxVlyqThLLhVnyaXiLLlUnCWXirPkUnGWXCrOkkvFWXKpuMZcQWVZ5nF9sSZd/2qgLdfrGmjb\ntdvazD25VJwll4qz5FJxllwqzpJLxVlyqThLLhW36+fkEbEPeAS4Hng38F3gJeAU0APOAscy8/JC\nU0qa2bg9+e3AvzPzEHAE+DFwAjjeX9cBji42oqS9GFfyXwD3Di1fBA4CZ/rLp4HDC8glaU52PVzP\nzP8ARMQa8ARwHLgvMwfzJC8ABxaaUNKejD3xFhHXAs8AP8nMnwLD77/XgPPjfka3231r/nSv19vx\na1lGbX9UprZnbWPepn21ZWxHGXfi7f3Ab4GvZebv+qtfjIitzPw92+/TnxkXcHNz862gFX6Jok1Z\nB/ctQ9VfUGnL2I7K0tktZET8EPgc8Leh1XcB9wP7gXPAVzLz0piAvUGINgzWgCWfjiVfnAlLvuOD\ndi35vFjy2VjyZmjL2I4quZNhpOIsuVTcO+4vw6j5lnnWelJNzDQp9+RScZZcKs6SS8VZcqk4Sy4V\nZ8ml4iy5VJwll4qz5FJxllwqzpJLxVlyqThLLhVnyaXiLLlUnCWXirPkUnGWXCrOkkvFWXKpOEsu\nFWfJpeIsuVScJZeKs+RScV5BZQZtuVCfdjfp/2ObLs64E/fkUnGWXCrOkkvFWXKpOEsuFWfJpeIs\nuVTc2M/JI+JK4CQQwCXgDqADnAJ6wFngWGZeXlxMSbOaZE9+K0Bm3gR8BzjR/zqemYfYLvzRhSWU\ntCdjS56ZTwNf7S9eB7wMHATO9NedBg4vJJ2kPZtoWmtmXoyIx4DPAJ8FPpWZvf7dF4ADu31/t9tl\nY2MD2J4iuErTbn/Veaex6qxtG9tptr/qrHsx8dz1zPxiRHwT+DNw9dBda8D53b53c3MT2H0O8LIG\ncZo5yG2as1xpbJuWty3Pg1HjNvZwPSI+HxH39BdfBy4Dz0fEVn/dEeDZOWSUtACdca+aEfEe4FHg\nA8A+4HvAObbPuO/v3/5KZl4auZFOpwftevWG9ryCQ62xbVretjwPer3ejiHHlnweLPniVRrbpuVt\ny/NgVMmdDCMVZ8ml4t5xfxmmTR/ztOEQcVibxnba7a86616eC+7JpeIsuVScJZeKs+RScZZcKs6S\nS8VZcqk4Sy4VZ8ml4iy5VJwll4qz5FJxllwqzpJLxVlyqThLLhVnyaXiLLlUnCWXirPkUnGWXCrO\nkkvFWXKpOEsuFWfJpeIacwWVJl4tZNSF7lZ9NY2m8mKSzeSeXCrOkkvFWXKpOEsuFWfJpeIsuVTc\nRB+hRcQ1wAvALcBF4BTQA84CxzLz8qICStqbsXvyiNgHPAS80V91AjiemYeADnB0cfEk7dUkh+v3\nAQ8C/+ovHwTO9G+fBg4vIJekOdn1cD0ivgS8kpm/iYh7+qs7mTmY5nMBODBuI91ul42NDaAdM4SG\nrTLvtNte9di2Le80Vp11L9sf9578TqAXEYeBjwCPA9cM3b8GnB+3kc3NTaBdUxlh9dNa5zVNtG15\nm6YtYzsqy66H65l5c2Z+IjO3gL8CXwBOR8RW/yFHgGenyCppyWb5BZW7gZMRsR84Bzwx30iS5qmz\njMONTqfTg3YdooGH69PycH1xJjxc3/FBToaRirPkUnGN+aMRq/6IYpSm5mqitn2E1pa3C7C3sXJP\nLhVnyaXiLLlUnCWXirPkUnGWXCrOkkvFWXKpOEsuFWfJpeIsuVScJZeKs+RScZZcKs6SS8VZcqk4\nSy4VZ8ml4iy5VJwll4qz5FJxllwqzpJLxVlyqThLLhXXmCuoNPFqFm26KN9umvhvcGznb6brk0tq\nP0suFWfJpeIsuVScJZeKs+RScZZcKs6SS8V1Rn2ALqkG9+RScZZcKs6SS8VZcqk4Sy4VZ8ml4pby\n++QRcQXwAPBh4E3gy5n592Vse1oRcQPw/czciogPAaeAHnAWOJaZl1eZDyAi9gGPANcD7wa+C7xE\nA7MCRMSVwEkggEvAHUCHhuYFiIhrgBeAW4CLNDjrOMvak38auCozPwZ8C/jBkrY7lYj4BvAwcFV/\n1QngeGYeYvtJeXRV2d7mduDf/VxHgB/T3KwAtwJk5k3Ad9jO2ti8/RfRh4A3+qsam3USyyr5x4Ff\nA2Tmn4CPLmm70/oHcNvQ8kHgTP/2aeDw0hPt7BfAvUPLF2luVjLzaeCr/cXrgJdpcF7gPuBB4F/9\n5SZnHWtZJX8v8OrQ8qWIaMyfnhrIzCeB/w6t6mTmYErgBeDA8lP9v8z8T2ZeiIg14AngOA3NOpCZ\nFyPiMeBHbGduZN6I+BLwSmb+Zmh1I7NOalklfw1YG95uZl5c0rb3Yvh91xpwflVB3i4irgWeAX6S\nmT+lwVkHMvOLwDrb78+vHrqrSXnvBG6JiN8DHwEeB64Zur9JWSeyrJL/EfgkQETcCHSXtN29ejEi\ntvq3jwDPrjDLWyLi/cBvgW9m5iP91Y3MChARn4+Ie/qLr7P9gvR8E/Nm5s2Z+YnM3AL+CnwBON3E\nrJNa1iHzU2y/Oj7H9omLO5a03b26GzgZEfuBc2wfZjbBt4H3AfdGxOC9+V3A/Q3MCvBL4NGI+AOw\nD/g62xmbOLY7aerzYCL+FppUnJNhpOIsuVScJZeKs+RScZZcKs6SS8VZcqk4Sy4V9z+JTZbDN9Vx\nNgAAAABJRU5ErkJggg==\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1a335296f60>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "mazeGen_BrkCir(5,5);"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 179,
   "metadata": {},
   "outputs": [
    {
     "ename": "NameError",
     "evalue": "name '_176' is not defined",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mNameError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-179-caf329c45565>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0m_176\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mNameError\u001b[0m: name '_176' is not defined"
     ]
    }
   ],
   "source": [
    "_176"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 206,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[array([11,  1])]"
      ]
     },
     "execution_count": 206,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "G.edgesOf(v1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 207,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 208,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 208,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "random.randint(0,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 242,
   "metadata": {},
   "outputs": [],
   "source": [
    "vers_in_circle.pop?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 236,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[array([7, 2]), array([6, 3]), array([7, 4]), array([8, 3])]"
      ]
     },
     "execution_count": 236,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "G.edgesOf(v)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 238,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "((7, 3), array([6, 3]))"
      ]
     },
     "execution_count": 238,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "v,e"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 229,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 229,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(G.edgesOf((1,1)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 237,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "unsupported operand type(s) for -: 'tuple' and 'tuple'",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-237-d047803edf93>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mG\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mremove_edge\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;32m<ipython-input-233-1befbb92f4af>\u001b[0m in \u001b[0;36mremove_edge\u001b[1;34m(self, v1, v2)\u001b[0m\n\u001b[0;32m     25\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     26\u001b[0m     \u001b[1;32mdef\u001b[0m \u001b[0mremove_edge\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mv1\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mv2\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 27\u001b[1;33m         \u001b[0mdelta\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;33m(\u001b[0m\u001b[1;33m*\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mv2\u001b[0m \u001b[1;33m-\u001b[0m \u001b[0mv1\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     28\u001b[0m         \u001b[0mmemmap\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;33m{\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m-\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;36m2\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m,\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;36m3\u001b[0m\u001b[1;33m}\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     29\u001b[0m         \u001b[0mind\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mmemmap\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mdelta\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mTypeError\u001b[0m: unsupported operand type(s) for -: 'tuple' and 'tuple'"
     ]
    }
   ],
   "source": [
    "G.remove_edge((1,0),(1,1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import random  \n",
    "import numpy as np  \n",
    "from matplotlib import pyplot as plt  \n",
    "import matplotlib.cm as cm  \n",
    "def mazeGen_Prim(num_rows=20, num_cols=20):  \n",
    "\n",
    "    # The array M is going to hold the array information for each cell.  \n",
    "    # The first four coordinates tell if walls exist on those sides   \n",
    "    # and the fifth indicates if the cell has been visited in the search.  \n",
    "    # M(LEFT, UP, RIGHT, DOWN, CHECK_IF_VISITED)  \n",
    "    M = np.zeros((num_rows,num_cols,5), dtype=np.uint8)  \n",
    "\n",
    "    # The array image is going to be the output image to display  \n",
    "    image = np.zeros((num_rows*10,num_cols*10), dtype=np.uint8)  \n",
    "\n",
    "    # Set starting row and column  \n",
    "    r = 0  \n",
    "    c = 0  \n",
    "    history = [(r,c)] # The history is the stack of visited locations  \n",
    "\n",
    "    # Trace a path though the cells of the maze and open walls along the path.  \n",
    "    # We do this with a while loop, repeating the loop until there is no history,   \n",
    "    # which would mean we backtracked to the initial start.  \n",
    "    while history:   \n",
    "        #random choose a candidata cell from the cell set histroy  \n",
    "        r,c = random.choice(history)  \n",
    "        M[r,c,4] = 1 # designate this location as visited  \n",
    "        history.remove((r,c))  \n",
    "        check = []  \n",
    "        # If the randomly chosen cell has multiple edges   \n",
    "        # that connect it to the existing maze,   \n",
    "        if c > 0:  \n",
    "            if M[r,c-1,4] == 1:  \n",
    "                check.append('L')  \n",
    "            elif M[r,c-1,4] == 0:  \n",
    "                history.append((r,c-1))  \n",
    "                M[r,c-1,4] = 2  \n",
    "        if r > 0:  \n",
    "            if M[r-1,c,4] == 1:   \n",
    "                check.append('U')   \n",
    "            elif M[r-1,c,4] == 0:  \n",
    "                history.append((r-1,c))  \n",
    "                M[r-1,c,4] = 2  \n",
    "        if c < num_cols-1:  \n",
    "            if M[r,c+1,4] == 1:   \n",
    "                check.append('R')  \n",
    "            elif M[r,c+1,4] == 0:  \n",
    "                history.append((r,c+1))  \n",
    "                M[r,c+1,4] = 2   \n",
    "        if r < num_rows-1:  \n",
    "            if M[r+1,c,4] == 1:   \n",
    "                check.append('D')   \n",
    "            elif  M[r+1,c,4] == 0:  \n",
    "                history.append((r+1,c))  \n",
    "                M[r+1,c,4] = 2  \n",
    "\n",
    "        # select one of these edges at random.  \n",
    "        if len(check):  \n",
    "            move_direction = random.choice(check)  \n",
    "            if move_direction == 'L':  \n",
    "                M[r,c,0] = 1  \n",
    "                c = c-1  \n",
    "                M[r,c,2] = 1  \n",
    "            if move_direction == 'U':  \n",
    "                M[r,c,1] = 1  \n",
    "                r = r-1  \n",
    "                M[r,c,3] = 1  \n",
    "            if move_direction == 'R':  \n",
    "                M[r,c,2] = 1  \n",
    "                c = c+1  \n",
    "                M[r,c,0] = 1  \n",
    "            if move_direction == 'D':  \n",
    "                M[r,c,3] = 1  \n",
    "                r = r+1  \n",
    "                M[r,c,1] = 1  \n",
    "\n",
    "    # Open the walls at the start and finish  \n",
    "    M[0,0,0] = 1  \n",
    "    M[num_rows-1,num_cols-1,2] = 1  \n",
    "\n",
    "    # Generate the image for display  \n",
    "    for row in range(0,num_rows):  \n",
    "        for col in range(0,num_cols):  \n",
    "            cell_data = M[row,col]  \n",
    "            for i in range(10*row+2,10*row+8):  \n",
    "                image[i,range(10*col+2,10*col+8)] = 255  \n",
    "            if cell_data[0] == 1:   \n",
    "                image[range(10*row+2,10*row+8),10*col] = 255  \n",
    "                image[range(10*row+2,10*row+8),10*col+1] = 255  \n",
    "            if cell_data[1] == 1:   \n",
    "                image[10*row,range(10*col+2,10*col+8)] = 255  \n",
    "                image[10*row+1,range(10*col+2,10*col+8)] = 255  \n",
    "            if cell_data[2] == 1:   \n",
    "                image[range(10*row+2,10*row+8),10*col+9] = 255  \n",
    "                image[range(10*row+2,10*row+8),10*col+8] = 255  \n",
    "            if cell_data[3] == 1:   \n",
    "                image[10*row+9,range(10*col+2,10*col+8)] = 255  \n",
    "                image[10*row+8,range(10*col+2,10*col+8)] = 255  \n",
    "\n",
    "\n",
    "    # Display the image  \n",
    "    plt.imshow(image, cmap = cm.Greys_r, interpolation='none')  \n",
    "    plt.show()\n",
    "    return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Code by jollysoul  \n",
    "  \n",
    "import random  \n",
    "import numpy as np  \n",
    "from matplotlib import pyplot as plt  \n",
    "import matplotlib.cm as cm  \n",
    "def mazeGen_ReBT(num_rows=20, num_cols=20):        \n",
    "  \n",
    "    # The array M is going to hold the array information for each cell.  \n",
    "    # The first four coordinates tell if walls exist on those sides   \n",
    "    # and the fifth indicates if the cell has been visited in the search.  \n",
    "    # M(LEFT, UP, RIGHT, DOWN, CHECK_IF_VISITED)  \n",
    "    M = np.zeros((num_rows,num_cols,5), dtype=np.uint8)  \n",
    "      \n",
    "    # The array image is going to be the output image to display  \n",
    "    image = np.zeros((num_rows*10,num_cols*10), dtype=np.uint8)  \n",
    "      \n",
    "    # Set starting row and column  \n",
    "    r = 0  \n",
    "    c = 0  \n",
    "    history = [(r,c)] # The history is the stack of visited locations  \n",
    "      \n",
    "    # Trace a path though the cells of the maze and open walls along the path.  \n",
    "    # We do this with a while loop, repeating the loop until there is no history,   \n",
    "    # which would mean we backtracked to the initial start.  \n",
    "    while history:   \n",
    "        M[r,c,4] = 1 # designate this location as visited  \n",
    "        # check if the adjacent cells are valid for moving to  \n",
    "        check = []  \n",
    "        if c > 0 and M[r,c-1,4] == 0:  \n",
    "            check.append('L')    \n",
    "        if r > 0 and M[r-1,c,4] == 0:  \n",
    "            check.append('U')  \n",
    "        if c < num_cols-1 and M[r,c+1,4] == 0:  \n",
    "            check.append('R')  \n",
    "        if r < num_rows-1 and M[r+1,c,4] == 0:  \n",
    "            check.append('D')      \n",
    "          \n",
    "        if len(check): # If there is a valid cell to move to.  \n",
    "            # Mark the walls between cells as open if we move  \n",
    "            history.append([r,c])  \n",
    "            move_direction = random.choice(check)  \n",
    "            if move_direction == 'L':  \n",
    "                M[r,c,0] = 1  \n",
    "                c = c-1  \n",
    "                M[r,c,2] = 1  \n",
    "            if move_direction == 'U':  \n",
    "                M[r,c,1] = 1  \n",
    "                r = r-1  \n",
    "                M[r,c,3] = 1  \n",
    "            if move_direction == 'R':  \n",
    "                M[r,c,2] = 1  \n",
    "                c = c+1  \n",
    "                M[r,c,0] = 1  \n",
    "            if move_direction == 'D':  \n",
    "                M[r,c,3] = 1  \n",
    "                r = r+1  \n",
    "                M[r,c,1] = 1  \n",
    "        else: # If there are no valid cells to move to.  \n",
    "        # retrace one step back in history if no move is possible  \n",
    "            r,c = history.pop()  \n",
    "          \n",
    "               \n",
    "    # Open the walls at the start and finish  \n",
    "    M[0,0,0] = 1  \n",
    "    M[num_rows-1,num_cols-1,2] = 1  \n",
    "          \n",
    "    # Generate the image for display  \n",
    "    for row in range(0,num_rows):  \n",
    "        for col in range(0,num_cols):  \n",
    "            cell_data = M[row,col]  \n",
    "            for i in range(10*row+2,10*row+8):  \n",
    "                image[i,range(10*col+2,10*col+8)] = 255  \n",
    "            if cell_data[0] == 1:   \n",
    "                image[range(10*row+2,10*row+8),10*col] = 255  \n",
    "                image[range(10*row+2,10*row+8),10*col+1] = 255  \n",
    "            if cell_data[1] == 1:   \n",
    "                image[10*row,range(10*col+2,10*col+8)] = 255  \n",
    "                image[10*row+1,range(10*col+2,10*col+8)] = 255  \n",
    "            if cell_data[2] == 1:   \n",
    "                image[range(10*row+2,10*row+8),10*col+9] = 255  \n",
    "                image[range(10*row+2,10*row+8),10*col+8] = 255  \n",
    "            if cell_data[3] == 1:   \n",
    "                image[10*row+9,range(10*col+2,10*col+8)] = 255  \n",
    "                image[10*row+8,range(10*col+2,10*col+8)] = 255  \n",
    "              \n",
    "      \n",
    "    # Display the image  \n",
    "    plt.imshow(image, cmap = cm.Greys_r, interpolation='none')  \n",
    "    plt.show()\n",
    "    \n",
    "    return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Code by jollysoul  \n",
    "  \n",
    "import random  \n",
    "import numpy as np  \n",
    "from matplotlib import pyplot as plt  \n",
    "import matplotlib.cm as cm  \n",
    "  \n",
    "#这个函数将当前区域划分为四个小区域，并随机的在三个区域挖洞，  \n",
    "#让四个区域彼此联通，分隔与挖洞点都是随机生成的。  \n",
    "def Recursive_division(r1, r2, c1, c2, M, image):  \n",
    "    if r1 < r2 and c1 < c2:  \n",
    "        rm = random.randint(r1, r2-1)  \n",
    "        cm = random.randint(c1, c2-1)  \n",
    "        cd1 = random.randint(c1,cm)  \n",
    "        cd2 = random.randint(cm+1,c2)  \n",
    "        rd1 = random.randint(r1,rm)  \n",
    "        rd2 = random.randint(rm+1,r2)  \n",
    "        d = random.randint(1,4)  \n",
    "        if d == 1:  \n",
    "            M[rd2, cm, 2] = 1  \n",
    "            M[rd2, cm+1, 0] = 1  \n",
    "            M[rm, cd1, 3] = 1  \n",
    "            M[rm+1, cd1, 1] = 1  \n",
    "            M[rm, cd2, 3] = 1  \n",
    "            M[rm+1, cd2, 1] = 1  \n",
    "        elif d == 2:  \n",
    "            M[rd1, cm, 2] = 1  \n",
    "            M[rd1, cm+1, 0] = 1  \n",
    "            M[rm, cd1, 3] = 1  \n",
    "            M[rm+1, cd1, 1] = 1  \n",
    "            M[rm, cd2, 3] = 1  \n",
    "            M[rm+1, cd2, 1] = 1  \n",
    "        elif d == 3:  \n",
    "            M[rd1, cm, 2] = 1  \n",
    "            M[rd1, cm+1, 0] = 1  \n",
    "            M[rd2, cm, 2] = 1  \n",
    "            M[rd2, cm+1, 0] = 1  \n",
    "            M[rm, cd2, 3] = 1  \n",
    "            M[rm+1, cd2, 1] = 1  \n",
    "        elif d == 4:  \n",
    "            M[rd1, cm, 2] = 1  \n",
    "            M[rd1, cm+1, 0] = 1  \n",
    "            M[rd2, cm, 2] = 1  \n",
    "            M[rd2, cm+1, 0] = 1  \n",
    "            M[rm, cd1, 3] = 1  \n",
    "            M[rm+1, cd1, 1] = 1  \n",
    "  \n",
    "        Recursive_division(r1, rm, c1, cm, M, image)  \n",
    "        Recursive_division(r1, rm, cm+1, c2, M, image)  \n",
    "        Recursive_division(rm+1, r2, cm+1, c2, M, image)  \n",
    "        Recursive_division(rm+1, r2, c1, cm, M, image)  \n",
    "  \n",
    "    elif r1 < r2:  \n",
    "        rm = random.randint(r1, r2-1)  \n",
    "        M[rm,c1,3] = 1  \n",
    "        M[rm+1,c1,1] = 1  \n",
    "        Recursive_division(r1, rm, c1, c1, M, image)  \n",
    "        Recursive_division(rm+1, r2, c1, c1, M, image)  \n",
    "    elif c1 < c2:  \n",
    "        cm = random.randint(c1,c2-1)  \n",
    "        M[r1,cm,2] = 1  \n",
    "        M[r1,cm+1,0] = 1  \n",
    "        Recursive_division(r1, r1, c1, cm, M, image)  \n",
    "        Recursive_division(r1, r1, cm+1, c2, M, image)  \n",
    "\n",
    "        \n",
    "        \n",
    "def mazeGen_ReD(num_rows=20, num_cols=20):  \n",
    "    \n",
    "    r1 = 0  \n",
    "    r2 = num_rows-1  \n",
    "    c1 = 0  \n",
    "    c2 = num_cols-1  \n",
    "\n",
    "    # The array M is going to hold the array information for each cell.  \n",
    "    # The first four coordinates tell if walls exist on those sides   \n",
    "    # and the fifth indicates if the cell has been visited in the search.  \n",
    "    # M(LEFT, UP, RIGHT, DOWN, CHECK_IF_VISITED)  \n",
    "    M = np.zeros((num_rows,num_cols,5), dtype=np.uint8)  \n",
    "\n",
    "    # The array image is going to be the output image to display  \n",
    "    image = np.zeros((num_rows*10,num_cols*10), dtype=np.uint8)  \n",
    "\n",
    "    Recursive_division(r1, r2, c1, c2, M, image)    \n",
    "\n",
    "    # Open the walls at the start and finish  \n",
    "    M[0,0,0] = 1  \n",
    "    M[num_rows-1,num_cols-1,2] = 1  \n",
    "\n",
    "    # Generate the image for display  \n",
    "    for row in range(0,num_rows):  \n",
    "        for col in range(0,num_cols):  \n",
    "            cell_data = M[row,col]  \n",
    "            for i in range(10*row+2,10*row+8):  \n",
    "                image[i,range(10*col+2,10*col+8)] = 255  \n",
    "            if cell_data[0] == 1:   \n",
    "                image[range(10*row+2,10*row+8),10*col] = 255  \n",
    "                image[range(10*row+2,10*row+8),10*col+1] = 255  \n",
    "            if cell_data[1] == 1:   \n",
    "                image[10*row,range(10*col+2,10*col+8)] = 255  \n",
    "                image[10*row+1,range(10*col+2,10*col+8)] = 255  \n",
    "            if cell_data[2] == 1:   \n",
    "                image[range(10*row+2,10*row+8),10*col+9] = 255  \n",
    "                image[range(10*row+2,10*row+8),10*col+8] = 255  \n",
    "            if cell_data[3] == 1:   \n",
    "                image[10*row+9,range(10*col+2,10*col+8)] = 255  \n",
    "                image[10*row+8,range(10*col+2,10*col+8)] = 255  \n",
    "\n",
    "\n",
    "    # Display the image  \n",
    "    plt.imshow(image, cmap = cm.Greys_r, interpolation='none')  \n",
    "    plt.show()\n",
    "    \n",
    "    return image"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAP8AAAD6CAYAAABuxZF5AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAEiVJREFUeJzt3X2sHNV5x/HvXlxAKBfyIpoqKgg1\nxE+lIhFMAqRNjSUTWcSVQEmlWFWoEguRRFZU2rShCpFcqv4TBbty3iAFU/pCBCmOlaDItVuFEuNA\nLDmmOBV9eItKW5WGUIEtaADb2z92br2+ur7zds6cmT2/j3Sl3b1nz5zZ2WfPvDxzzmg8HiMi+ZlL\n3QARSUPBL5IpBb9IphT8IplS8ItkSsEvkqkVISszsznga8DFwGvA9e7+dMhliEgYoXv+a4Ez3f19\nwB8DWwLXLyKhjMfjYH8rV67cunLlyg1Tz/9zufKHDh0aAzP5N6vrNqvrNcvrdqr4C7rbD5wNvDz1\n/JiZrXD3o0sVvuiii5jlDMNZXbdZXS+YvXUbjUan/F/o4D8MzE89nztV4Ke2+EMJsdGn6xyPx4xG\no1PWu9RGqVp2ubbGLlu2XnXF3g5l9dbZZkOzXOBD+GP+fcAHAczsCuBQ4PpFJJDQPf9O4ANm9gNg\nBHw8cP0iEsgo8S5OsoVrt1+7/YvLzupu/3g8XnL/X0k+IplS8ItkSsEvkqnQJ/xqKzvGanMMG0KM\nOmddm8+sznu7Pjafte+Cen6RTCn4RTKl4BfJVPLr/CGP+UX6ome5GbrOLyInKPhFMqXgF8mUgl8k\nUwp+kUwp+EUylTy9t65Q6Z9tUjVD3B7a1S29ddS5pTd0vU3U+Wyr1jdrKbzLUc8vkikFv0imFPwi\nmRrcMf9Qjh9TqZP+HPv8QNt6mtbbJgU8Rfp4nWWGbF+j4DezXwDuAi4AzgD+DPgP4AHgqaLYbe5+\nX4A2ikgETXv+jwIvuvt1ZvY24CDwp8BWd9cUXSID0DT4/w64f+r5UeBSwMzsGia9/43ufqRl+0Qk\nkla39JrZPPAd4A4mu/+Pu/sBM7sZeIu7/2FJFbo/VySiItck7C29ZnYe8CDwN+7+DWCnux8o/r0T\nuKRq48r+P/3XddnF5aqWXXgeut6QJyCbfF4Lj0PVG6u9Emm6LjN7O7AHuMnd7ype3m1mlxWP1wIH\nlnyziPRCo91+M9sGfAT416mXbwa+CLwOPA/c4O6HS6oKOpJPjLJtZ3+pI8blxhQz9qQecXkps7rN\nKta35JtmahgvBX/1OpeqV8E/vG1WsT4N4yUiJyj4RTLV+/TeWIclMepdXGefU2Drmm5DzEPFWIdq\nVZeX4nbpWPVEOdsvIsOn4BfJlIJfJFMKfpFMKfhFMtX7s/2xzl7HmAOwbcJIjMEq6rShStkqST5t\n2hBLnXULXW/dOrqau1I9v0imFPwimVLwi2RKwS+Sqd6f8BvSiaW2qaJdpBwv14YU6ch1xBiVN9Z2\nSP1drEI9v0imFPwimVLwi2RKwS+SKQW/SKZ6f7a/q7OmQ0qDTTzuItDNoCFdLbOqNsvvKk29jsbB\nb2YHgZeLpz8Bvg5sYzJ7zx53v6Vxq0QkuqYTdZ4J4O5rpl57DPgw8CzwXTNb5e4/CtFIEQmvac9/\nMXCWme0p6vgT4Ax3fwbAzHYzmbijNPjLdmH7mDASYhl9WK+mZVMddqQed7EPh1t127DcYUHT4H8V\nuBW4E3gXsAt4aer/R4Bfqdq4FIMmxj5+LDvm79NY/HXKNrnttY6uvwtL3YYdY5vV0dX3tmnwPwk8\n7e5j4Ekzexl469T/5zn5x6CxWOm9MX7Fhzwib52yZe+LMVZCWZtC1ZGi50/1vWl6qW8jsAXAzN4B\nnAW8YmbvNLMRsA7Y27BuEelA055/O3C3mT3MZJrtjcBx4B7gNCZn+38YpokiEkPv5+qro6vdzSrL\nb3Kdv0q9C3WHKBtLrDb0Yd1iiP15aa4+ETmJgl8kU4NL7+367H8f0zJjLSfWpb4+XAWJdakvxvem\nq++Gen6RTCn4RTKl4BfJlIJfJFO9P+HXRoz0z+W0PVHTdXub1psqvXdI1/XbfG9i5UUspp5fJFMK\nfpFMKfhFMqXgF8mUgl8kU70429+HFNrUo7fEWlboUWFSpvdWPSve9nMMsR1SncGvQz2/SKYU/CKZ\nUvCLZKoXx/wpBniMMTtOrAy/vmXM9WUAz1Nps7wUIz7HGm5dGX4isqSmM/Z8DPhY8fRM4N3A7wBf\nBP69eH2zuz/Usn0iEknrATzN7KvAPwPnAwfdfUeNtycbwDPGrmlXo8L0/QaXWR3Ac2jbrGwAz1bB\nb2bvAW519zVmtovJ8N1nA/uBm9z9aEkV/f4Wiwxc0QFFGb33c8DCbLz/AHwaWA28Cfhk1caFMhqN\nTvoLVbbJ8heeV11+nbJ9F6u9qT+HoW2zaCf8zOzNwK+6+4PFS3e5+7PFFF7fBi5pWreIxNem518N\n/CNAMUXX42b2y8X/1gIHWrYN6O4XdKlf9bp/XQnVpiZlqyw/VnuratpDLzxvu6y2dYQqW6ZN8Bvw\nLEDR218PfMvMHmIyd98drVomIlH1frquOmdN25QNrS9jwM/yFN2hP9sZnlZd03WJyAm9SO8NJUaa\nZJ1epE65VCmdTdUZwLOOIVy9WE4fbgVvSj2/SKYU/CKZUvCLZErBL5IpBb9IphT8IpmaqUt9sZIl\nmiw/ZsJILFXa1CTJJ9alyj5+hiF09Rmo5xfJlIJfJFMKfpFMzdQx/5DEmr891s0nTcp1XdeCLlKc\nY+rq5jX1/CKZUvCLZErBL5IpBb9IphT8IplS8ItkqtKlPjO7HPhCMTnHhcDdTCbc+DGwyd2Pm9lm\nYD1wFLjR3fdXbUSsSzN9ThVtM0JQ2+W0KRs6vbePKbp9bFMMpT2/mX0WuJPJnHwAW4HPu/tvAiPg\nGjNbBVwJXA5sAL4ap7kiEkqV3f5ngA9NPb8UWJiAcxdwFfB+YI+7j939OWCFmZ0btKUiElTpbr+7\n7zCzC6ZeGhXj9AMcAc5hMj/fi1NlFl5/oaz+vmeLtVl+igE8u/gMct1mXbUhZNnlDmGapPcen3o8\nD7wEHC4eL369VNm4/bH0cQz41IGwnMXj9g+hrdNCbLOhiZHee9DM1hSPrwb2AvuAdWY2Z2bnA3Pu\n/rMGdYtIR5r0/J8B7jCz04EngPvd/ZiZ7QUeYfKDsilgG0Ukgt5P1xWLdvvr0W7/8Gi6LhFZkoJf\nJFMKfpFM9WIknzrplDmmivZhaug6+jbyUN3lhPg+drXN2lDPL5IpBb9IphT8IpnqxTF/rOuqXV+v\nrZMnHuo8R5t6+yDGurWtM8b3po/fBfX8IplS8ItkSsEvkikFv0imFPwimVLwi2SqF5f6+nDZK8Tl\nnaVuD236/hRSLD/GMrscDbrry8lK7xWR1hT8IplS8ItkqhfH/CnSe2OkitZ5f9OhpsraNIRbSWO3\noQ/p0H1IWS9btybTdb0b+DJwDHgN+F13/28z+xLwG0zG7Ae4xt1frtxSEelUafAX03VdB7xSvLQN\n+LS7P2ZmnwBuAv4AWAWs05DdIsPQZLquDe7+WPF4BfBzM5sD3gX8hZntM7ONgdspIoFVGrq7mK7r\nXne/Yuq1Xwe2A6uBnwO/x2QSz9OAB4GN7v54SdWzMUaySE8VQ5GHG7rbzD4C3A6sd/cXgFeBbe7+\nqrsfAb4HXFy1caGMRqOT/kKVbbL8hedVl1+nbNU2xCi78DhlG4awzZq2IXQ8LKf22X4z+yjwCWCN\nu/9P8fJK4N5iqu45JrP2/lXdukWkO7WC38xOA74EPAd8y8wAHnL3zWZ2D/Ao8Abw1+7+LyEaGGuE\n2abLH5ouU127bkOd5XV9+a+rz71NPPR+uq4217hDlG26EUNO19Wn6/xN7lkI3Yaysm2n66oj9dDd\nFbeZpusSkRMU/CKZ6kV6bwpVD3faHBYt99469cYqW8d0vbMyi+2pdD16byrq+UUypeAXyZSCXyRT\nCn6RTCn4RTLVi7P9fchCi5UwEiPJp44ICSPJknwWi5VlGGPg1z4MUruYen6RTCn4RTKl4BfJlIJf\nJFO9OOEXKvWxD6O2diHFKLux0nu7nlWpzTJinXiNVU9Ze9Xzi2RKwS+SKQW/SKYU/CKZUvCLZKrJ\ndF2rgAeAp4p/3+bu95nZZmA9cBS40d33h2hgrDH8yt4bqmxqIYeXhvjpvV3Pndd2DL+q+jgnYJPp\nulYBW919y1SZVcCVwOXAecAO4L2NWyUi0TWZrutSYL2Zfd/MtpvZPJNx+ve4+9jdnwNWmNm5Edor\nIoGU9vzuvqOYrmvBfuBOdz9gZjcDm4GXgBenyhwBzgFeKKu/bLdlaGPdVV3G0NZrVsfwW7wuKZJx\nYik7jGmS4bfT3V9aeMxkuu5vA/NTZeaZ/CCU6su4/aFp3P5+GdK4/SGWX6UNTc727zazy4rHa4ED\nwD5gnZnNmdn5wNzQpuoej8dB/xbqTK2sjXXrKauzD3+xPrMQdVSpt6t1bdLzfwr4ipm9DjwP3ODu\nh81sL/AIkx+UTa1aJSLRabquCmVj6Gq3v8+fQSx9GH2pjljbQdN1iciSFPwimVLwi2SqF4N51DGU\n9Muy48cu2lBXleVXWa/U67GUrtvUVap5G+r5RTKl4BfJlIJfJFMKfpFMDe6EX6gEiKr1tEnsWK5c\nrISaOvXGOgk15GShFG2PtUyN3isiS1Lwi2RKwS+SKQW/SKYU/CKZGtzZ/lBnnWPcRtnHUWFSpOGm\nvgW56XrFTMnuY8qzen6RTCn4RTKl4BfJVO+P+ft4K+SpLG5rqOPtPmTipf5s2+o6K7MPw6mVbbMm\n03XdC/xS8a8LgEfdfYOZfQd4G/AG8L/ufnXjVotIdLWn63L3DcXrbwEeBH6/KHoh8GvuPtzEbpGM\nNJmua8EtwJfd/b/M7O3Am4EHzOxhM/utkI0UkfBKg9/ddzDZlf9/ZvaLTCbsuLt46XRgC3Atkx+K\nPy/KlAp5R1OdCQ2qlo0xKUSX9YYyXV+ozzZW2VifbR2xPoO6bVhO0xN+vw18w92PFc+fB25396PA\nT83sIGDAT8sqqptUUVbXtFgJIzHGao9Vb4Qx4HszxVrX26yOIZzwa3qp7ypg16Ln3wQwszcBFwFP\nNKxbRDrQtOc34NmFJ+6+y8zWmdmjwHHgc6Hm6mtzianOe0Ncymqb3pt6hNlY7x1K2SYz9nQtZBsG\nN11XH9SZ+im10J9tX9YrhpjBH+vQp+KyNV2XiJyg4BfJVO/TexdLfdZ2OXXSe9u0IfXgn0MeoHOx\ntocwIT6LVIOuqucXyZSCXyRTCn6RTCn4RTKl4BfJlIJfJFODu9Q3y6P3NllOmdCj9TS5sWdouk4L\nX6yr7616fpFMKfhFMqXgF8lU74/5h5RK2nb03q7XtenyqoxMM1RDbvtiZeuinl8kUwp+kUwp+EUy\npeAXyZSCXyRTCn6RTPViAM9ZNKsDXc7qesHsrpsG8BSRk6Tu+UUkEfX8IplS8ItkSsEvkikFv0im\nFPwimVLwi2RKwS+SqSSDeZjZHPA14GLgNeB6d386RVtCMbODwMvF058AXwe2AUeBPe5+S6q2NWFm\nlwNfcPc1ZnYhcDcwBn4MbHL342a2GVjPZB1vdPf9yRpc0aL1WgU8ADxV/Ps2d79viOvVRKqRfK4F\nznT395nZFcAW4JpEbWnNzM4EcPc1U689BnwYeBb4rpmtcvcfpWlhPWb2WeA64JXipa3A5939n8zs\nduAaM/s34ErgcuA8YAfw3hTtrWqJ9VoFbHX3LVNlVjGw9Woq1W7/+4G/B3D3R4H3JGpHKBcDZ5nZ\nHjP7npmtBs5w92fcfQzsBtambWItzwAfmnp+KfBQ8XgXcBWTbbjH3cfu/hywwszO7baZtS21XuvN\n7Ptmtt3M5hnmejWSKvjP5sQuMsAxM+v9eILLeBW4FVgHfBL4y+K1BUeAcxK0qxF33wG8MfXSqPgR\ngxPrsngb9n4dl1iv/cAfuftqJntomxngejWVKvgPA/PT7XD3o4naEsKTwN8WvcWTTL48b536/zzw\nUpKWhXF86vHCuizehkNcx53ufmDhMXAJs7FelaQK/n3ABwGKY/5DidoRykYm5y0ws3cAZwGvmNk7\nzWzEZI9gb8L2tXXQzNYUj69msi77gHVmNmdm5zP5Af9ZqgY2tNvMLiserwUOMBvrVUmqXe2dwAfM\n7AfACPh4onaEsh2428weZnJGfCOT3vIe4DQmx5A/TNi+tj4D3GFmpwNPAPe7+zEz2ws8wqQT2ZSy\ngQ19CviKmb0OPA/c4O6HZ2C9KtEtvSKZUpKPSKYU/CKZUvCLZErBL5IpBb9IphT8IplS8Itk6v8A\nWMFrLPwBT84AAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x2097870e4a8>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAP8AAAD6CAYAAABuxZF5AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAEelJREFUeJzt3X2MXNV5x/HvLi5YKAt5EU0VCYQa\n4qdSkRyWBJM0NZYgsogrGSWVYlWhSixEEllRadOGKkRyqfpPFOzKeYMUTN0XImhxrARFrt0qlBgH\nYskxxanow4uj0lSlIVR+ETSA7ekfc6eMV+ude++cc8+ZOb+PtNLM7N1zn3PvPnPuy7nnzPR6PUSk\nPLOpAxCRNJT8IoVS8osUSskvUiglv0ihlPwihVoWsjAzmwW+DqwEXgVucvdnQ65DRMII3fLfACx3\n9/cBfwxsCVy+iITS6/WC/axYsWLrihUrNgy9/8+llj98+HAPmMqfaa3btNZrmut2tvwLetgPXAAc\nG3p/ysyWufvJxRa+/PLLmeYehtNat2mtF0xf3WZmZs76u9DJfxyYG3o/e7bEr2th8NOycxbbKTnX\nbRBvr9djZmZmImIdlnO8sSyV+BD+nH8/8CEAM7saOBy4fBEJJHTLvwv4oJn9AJgBPhG4fBEJZCbx\n4dDIleuwPw867J88Q/ts0eN/dfIRKZSSX6RQSn6RQoW+4NdYyPPHUbc2uhTy3Lirek3afgi9bUft\ns5z+vwbG2QZq+UUKpeQXKZSSX6RQyc/5Q2py/tNF/4FY95aXKjfHfhFdX0voss5db9+Q1x3U8osU\nSskvUiglv0ihlPwihVLyixRKyS9SqKm61TfOba4mt1DqdP8cdBXNWQ7xdbXPutakXqnqoZZfpFBK\nfpFCKflFCjVV5/xN1D23HOdaQA5da5uoG++o5VJ0a24rh+sGqf5PWiW/mf0ScC9wKXAe8GfAT4GH\ngGeqxe509wcCxCgiEbRt+T8GvOTuN5rZ24BDwJ8CW91dU3SJTIC2yf/3wIND708CVwJmZuvpt/63\nuPuJMeMTkUjGGrrbzOaA7wB30z/8f9LdD5rZbcBb3P0PRxQxWSfFIhOmGpYs7NDdZnYx8DDwN+7+\nTWCXux+sfr0LuKJucKN+P/wTatm6FpaZ4gJRrG2Qul45xLBw3UvF0OR/IXW9BjEspVXym9nbgb3A\nre5+b/XxHjO7qnp9LXBw0T8WkSy0Ouw3s23AR4F/G/r4NuBLwGvAC8DN7n58RFG9USPcph4Jtu36\nY3bvDTWST5v46oxKnMPtszbajN47CSP9nu2wP/l0Xbn8Iyn56687l30WWmnJrx5+IoVS8osUauK6\n9+bQZTZUN9jUunp8NvftMCxUrDnUOcrVfhGZfEp+kUIp+UUKpeQXKZSSX6RQE3e1fympO1aMO4Bn\n3Q4jXQ9MGlPqfTaszT7LKf6m1PKLFErJL1IoJb9IoZT8IoXK/oLfOBehQlzAijV6b+qnFXMxzsXL\nWPs3921Wl7r3isiilPwihVLyixRKyS9SKCW/SKGyuNqfasjmYaG7zNYZ666tkMOSd/G3XXcxjnUF\nP8euvOPUq3Xym9kh4Fj19ifAN4Bt9Gfv2evut7eOSkSiaztR53IAd18z9NkTwEeAI8B3zWze3X8U\nIkgRCa9ty78SON/M9lZl/Alwnrs/B2Bme+hP3DEy+VN1qOhiHL6l/rZJublNeT1N+6xJx6xJ6/wz\n6inFtsn/CnAHcA/wLmA3cHTo9yeAX61TUMzzqBDj2487bn/qMeBjjdsfS6x9VmfZNvsstXH2b9vk\nfxp41t17wNNmdgx469Dv5zjzy2BJOX+jdjXCbagYulhPyHhyH2+g7fpjdEVerNxxtL3VtxHYAmBm\n7wDOB142s3ea2QywFtgXJkQRiaFty78d2GFmj9KfZnsjcBq4DziH/tX+H4YJUURiyH6uvlhiPyEW\n8pw/lliHpqljiHXOP04MsQ7765zza64+ETmDkl+kUFl0711KV7dXcriNk0MMZzN0CBlsVOKl1pNS\nDt2Ru6CWX6RQSn6RQin5RQql5BcpVPYX/HLoUtlW0/XnfH95uJxRZcZ6FqGucS+gdf1/k+qCqFp+\nkUIp+UUKpeQXKZSSX6RQSn6RQmV/tX8SBkVYTJtusHWXT7kNYo5KPErquzldjXbcVb3U8osUSskv\nUiglv0ihsj/n70qM86zUPQybSjGAZ+ptNM1Dd4+ill+kUG1n7Pk48PHq7XLg3cDvAF8C/qP6fLO7\nPzJmfCISydgDeJrZ14B/AS4BDrn7zgZ/PnIAzzYDFoZedpLksA1Sl5vD4KixhBzAc6zkN7P3AHe4\n+xoz201/+O4LgAPAre5+ckQR07FHRDJVNa5RRu/9PDCYjfcfgc8Aq4E3AZ+qG9yo3w//pFh2kuSw\nDVKXu3C5kvfvUlonv5m9Gfg1d3+4+uhedz9STeH1beCKtmWLSHzj3OpbDfwTQDVF15Nm9n53/yn9\nGXoPBoivM6Fbh1wm6gxlnNF7c4p/KbEnIc3NOIf9BhwBqFr7m4Bvmdkj9Ofuu3v88EQkluyn6+rq\nan9oubT8obdXTq1jrGnVJ4mm6xKRxort3hvjiCdWq5HjPeocHuk9m3Fia3q0mOO+qUstv0ihlPwi\nhVLyixRKyS9SKCW/SKGU/CKFyuJWX6xbZDncemsSw6R1MDmbrubq67pLdhNd7ctxYlXLL1IoJb9I\noZT8IoXK4pw/xhzyo3Q1jNckd/8MJdQDVnW3ZY6PS+c405RafpFCKflFCqXkFymUkl+kUEp+kUIp\n+UUKVetWn5mtAr5YTc5xGbCD/oQbPwY2uftpM9sMrANOAre4+4EQAabu8jppXY8nXYxbfznIsV4j\nW34z+xxwD/05+QC2Al9w998EZoD1ZjYPXAOsAjYAX4sTroiEUuew/zngw0PvrwQGE3DuBq4DPgDs\ndfeeuz8PLDOzi4JGKiJBjTzsd/edZnbp0Ecz1Tj9ACeAC+nPz/fS0DKDz18cVf6oQ5zUh3axBoNM\nXa9xhNxnMbbDOOsPtc9y6DE6aijyNt17Tw+9ngOOAser1ws/HynUI5SDsobFejQz53JzkHqW3rZl\nxnykN8U2iDFX3yEzW1O9vh7YB+wH1prZrJldAsy6+89blC0iHWnT8n8WuNvMzgWeAh5091Nmtg94\njP4XyqaAMYpIBNlP19WEDvvzkMMhb5syp/WwX9N1icgZlPwihVLyixQqi5F8ltLVuVPoMttM9xwj\nptDTlIeexrqr6zRd/n3u6xtQyy9SKCW/SKGU/CKFyv6cvyshzjWb9BOPJdajo12NdhxL3XhTXFNK\nNUuRWn6RQin5RQql5BcplJJfpFBKfpFCKflFCpXFrb4cRrINHcOox0PHWV/Oj8guVm7OmjzS29VI\nztmM3isi00nJL1IoJb9IobI450/RVTTGOiehS2cXYtUtdZfi1OsPHUOb6breDXwFOAW8Cvyuu/+3\nmX0Z+A36Y/YDrHf3Y8EiFZGgRiZ/NV3XjcDL1UfbgM+4+xNm9kngVuAPgHlgrYbsFpkMbabr2uDu\nT1SvlwG/MLNZ4F3AX5jZfjPbGDhOEQms1tDd1XRd97v71UOfvR/YDqwGfgH8Hv1JPM8BHgY2uvuT\nI4pOfxIlMsWqfgvhhu42s48CdwHr3P1F4BVgm7u/4u4ngO8BK+sGF8rMzMwZP11buO5QMTSpV+xl\nB69DibHPFpa5VLmx9lkTsf5vR5XV+Gq/mX0M+CSwxt3/p/p4BXB/NVX3LP1Ze/+qadki0p1GyW9m\n5wBfBp4HvmVmAI+4+2Yzuw94HHgd+Gt3/9cQAY7zTRjrWzyHEWZTm+bbmqlj6Gr92U/XlXpHLKZO\n3+9UffvHmcW15tRPjWPPYf822WfTRtN1icgZlPwihcqie+9SYp2W5DgabQ4x1BUq1ty6Wecw4nJX\nj1ar5RcplJJfpFBKfpFCKflFCqXkFylU9lf7x+m0EmP9KeQQw0I5xBS652DMTj45DnCill+kUEp+\nkUIp+UUKpeQXKVT2F/ya6KprZt31xIon56fkmopxQXec2FLMWpTqkWe1/CKFUvKLFErJL1IoJb9I\noZT8IoVqM13XPPAQ8Ez16zvd/QEz2wysA04Ct7j7gRgB59CtNHVX0dx1NVBK6O0benzCYTnOSdhm\nuq55YKu7bxlaZh64BlgFXAzsBN4bPFoRCabNdF1XAuvM7Ptmtt3M5uiP07/X3Xvu/jywzMwuihCv\niAQysuV3953VdF0DB4B73P2gmd0GbAaOAi8NLXMCuBB4cVT5ow5xJmlcu4VSjHPXxbIh91msZdvK\neWzCpuWOOo1p08Nvl7sfHbymP133t4G5oWXm6H8hjDSJ4/bXEfL8MfZY/E2WHTUfQZfxhhZzn4Uo\nc7Fyx9leba727zGzq6rX1wIHgf3AWjObNbNLgNlQU3X3er0oPzHWM278ORuOMVWsXfwfNF1PiNhT\nadPyfxr4qpm9BrwA3Ozux81sH/AY/S+UTQFjFJEIsp+uK5YYt6OaTNfVttxB2V0v20QOMdQ1zfts\n6FRN03WJyBuU/CKFUvKLFCqLwTxyGDH1bBaLLVa5qeXebbnu+W6s+HLcZ+NQyy9SKCW/SKGU/CKF\nUvKLFCqLC365d22ta2E9mtYrxAWscbZl3b/NfX/F2gY51DtkDGr5RQql5BcplJJfpFBKfpFCKflF\nCpXF1f6l5NilMudusLG7ttZ57HWcGJr8bYi7IIs90ptaV3d31PKLFErJL1IoJb9IobI/54/VqyrG\nXO+xHv/totdeTCmH5hqlSa/MWPs3lTbTdd0P/Er1q0uBx919g5l9B3gb8Drwv+5+fYyARSSMxtN1\nufuG6vO3AA8Dv18tehnw6+4+uV+FIgVpM13XwO3AV9z9v8zs7cCbgYfM7FEz+62QQYpIeCOT3913\n0j+U/39m9sv0J+zYUX10LrAFuIH+F8WfV8uMlMsEEKHLHLzvWqwJIZrUK/WkFLEmxshpwo06RsXX\n9oLfbwPfdPdT1fsXgLvc/STwMzM7BBjws1EFadz+sGKPxd+mk0/qbRAqhkm74Bdjui6A64DdC97/\nHYCZvQm4HHiqZdki0oG2Lb8BRwZv3H23ma01s8eB08Dnm8zVp9F705j0GMa9DbtYeaG2SQ7bdpQs\npuuKVniAQ9Mmyd/ksL+rf47QffBDH/bHSP62ZbZJ/tT7tw5N1yUiZ1DyixQqi+69OV857lLquuUw\ngGesslPXLYc7Wgup5RcplJJfpFBKfpFCKflFCqXkFymUkl+kUFnc6gulq1Fju9ZVbDmPSgxxtkMO\no/d21cV5IbX8IoVS8osUSskvUqjsz/mbnNOk7h4bS271Sjn6Uuwyc9jWIUceWopafpFCKflFCqXk\nFymUkl+kUEp+kUIp+UUKNdUDeKaUshtsTNNaL5jeumkATxE5Q+qWX0QSUcsvUiglv0ihlPwihVLy\nixRKyS9SKCW/SKGU/CKFSjKYh5nNAl8HVgKvAje5+7MpYgnFzA4Bx6q3PwG+AWwDTgJ73f32VLG1\nYWargC+6+xozuwzYAfSAHwOb3P20mW0G1tGv4y3ufiBZwDUtqNc88BDwTPXrO939gUmsVxupRvK5\nAVju7u8zs6uBLcD6RLGMzcyWA7j7mqHPngA+AhwBvmtm8+7+ozQRNmNmnwNuBF6uPtoKfMHd/9nM\n7gLWm9m/A9cAq4CLgZ3Ae1PEW9ci9ZoHtrr7lqFl5pmwerWV6rD/A8A/ALj748B7EsURykrgfDPb\na2bfM7PVwHnu/py794A9wLVpQ2zkOeDDQ++vBB6pXu8GrqO/D/e6e8/dnweWmdlF3YbZ2GL1Wmdm\n3zez7WY2x2TWq5VUyX8BbxwiA5wys+zHE1zCK8AdwFrgU8BfVp8NnAAuTBBXK+6+E3h96KOZ6ksM\n3qjLwn2YfR0XqdcB4I/cfTX9I7TNTGC92kqV/MeBueE43P1kolhCeBr426q1eJr+P89bh34/BxxN\nElkYp4deD+qycB9OYh13ufvBwWvgCqajXrWkSv79wIcAqnP+w4niCGUj/esWmNk7gPOBl83snWY2\nQ/+IYF/C+MZ1yMzWVK+vp1+X/cBaM5s1s0vof4H/PFWALe0xs6uq19cCB5mOetWS6lB7F/BBM/sB\nMAN8IlEcoWwHdpjZo/SviG+k31reB5xD/xzyhwnjG9dngbvN7FzgKeBBdz9lZvuAx+g3IptSBtjS\np4GvmtlrwAvAze5+fArqVYse6RUplDr5iBRKyS9SKCW/SKGU/CKFUvKLFErJL1IoJb9Iof4PlsAi\niSNOur4AAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x2097870ea90>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAP8AAAD6CAYAAABuxZF5AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAAEWhJREFUeJzt3X2sXEd5x/HvvXETK+ImvCilQiSK\nSvCD1EgmN4BDSx1LDrKCKzmCSliIVGBFAWRFDaWQCpDcVP2HErsybwkNTt2XoKSNsSBCrl1ECI5J\nsGScxlThyYtR01ZNKa38oqQk2N7+secq6+313XPOzpw558zvI620L3Nnn9mzz53zMjszMxgMEJH8\nzKYOQETSUPKLZErJL5IpJb9IppT8IplS8otkalnIysxsFvgKsBJ4CbjJ3Z8J+R4iEkbonv8GYLm7\nvxP4I2Br4PpFJJTBYBDstmLFim0rVqzYOPL435cqf+TIkQHQy1tf29bXdvW5befKv6C7/cBFwPGR\nx6fNbJm7n1qs8JVXXkmfRxj2tW19bRf0r20zMzPnfC108p8A5kYez54r8WMYb2jfNqT0U6zv7VKJ\nD+GP+Q8A7wEws2uAI4HrF5FAQvf8u4F3m9kPgBngw4HrF5FAZhLvGgd9c+32SxfF3u0fDAaL7v9r\nkI9IppT8IplS8otkKvQJv8omXY4YV+V4qGrdIQ0Gg6TvH8tCu5baDm1s97niHY21zjYrU29IIc8P\nqOcXyZSSXyRTSn6RTCU/5oelj1umOXZKfZ0/9fvHMqldqds97fF2iPi7cG5KPb9IppT8IplS8otk\nSskvkiklv0imlPwimWrFpb5YqlxCCT1Ms+/De9sg1uW0lN+bJqnnF8mUkl8kU0p+kUy1/ph/mqGW\nsYaZlq039TDXWFK1K8ZQ78XqjNG+Nv4Eulbym9mvAPcAlwMXAH8K/BvwIPB0UexOd78/QIwiEkHd\nnv+DwH+7+41m9jrgMPAnwDZ31xJdIh1QN/n/Hnhg5PEp4GrAzGwDw97/Vnc/OWV8IhLJVFN3m9kc\n8C3gboa7/0+4+yEz+wzwGnf/wwlV9POgWKQliinXwk7dbWaXAg8Bf+PuXwd2u/uh4uXdwFVlgwtl\nZmbmrFuMOrsweKOvym6HKttsvEys702qskuplfxm9npgH3Cbu99TPL3XzN5R3F8LHFr0j0WkFWrt\n9pvZduD9wE9Gnv4M8HngZeB54GZ3PzGhqkHVmWCbLtvk8N4uDBXtwvDeKpfvmpq9N+V3/Fy7/cmX\n61Lyx4shBiV/vRjamPwa4SeSKSW/SKZaP7w3tTYML27bMOEuDu89l/G2pGhbqs9TPb9IppT8IplS\n8otkSskvkiklv0imWnG2v6m1zJuMoS2DYUJPItGWdkGYbRZrkE/dGELVWYZ6fpFMKflFMqXkF8mU\nkl8kU6044RdrZtPUw2JTv/8kdeML2a4YJ7umPREYIoa2b3tQzy+SLSW/SKaU/CKZUvKLZErJL5Kp\nVpztjyXlMFTN4VdPlbqrnFGPNdS7C9vsXGonv5kdBo4XD38KfBXYznD1nn3ufvv04YlILHUX6lwO\n4O5rRp57HHgfcBT4tpnNu/uPQgQpIuHV7flXAhea2b6ijj8GLnD3ZwHMbC/DhTsmJv+kXbcqu3Zt\nG1ihOfzS6PO8i1XzYanDj7rJ/yJwB/A14M3AHuDYyOsngV8vU1HMeftT0jF/fH1da6GpfKib/E8B\nz7j7AHjKzI4Drx15fY6z/xkkEepDLKvuYhFVpeh527AIxTTK1pui50/1z7Tupb5NwFYAM3sDcCHw\ngpm9ycxmgHXA/jAhikgMdXv+HcBOM3uE4TLbm4AzwL3AeQzP9v8wTIgiEoPW6itRtqzFpoQKvZ7c\nUuViGln3Lep5mqYPv9pAa/WJSKOU/CKZ6vXw3hDauAsZ6+xw6nZNMs0hQpnPrC2XMZuKQT2/SKaU\n/CKZUvKLZErJL5IpnfBLpMs/WOqiEMN72zA2I+TJQPX8IplS8otkSskvkiklv0imlPwimdLZ/hpC\nnHFtaghnV2Y+qiP0dkg1vDfVrzbV84tkSskvkiklv0imenXM39SouViz7DY9WqxuPalGHJZ932lW\n3Al1jqQLozLV84tkqu6KPR8CPlQ8XA68FfgA8HngX4vnt7j7w1PGJyKRTD2Bp5l9Gfgn4DLgsLvv\nqvDnQSfwjKHujzn6NoFnFX2dwLOpepuawHOq5DeztwF3uPsaM9vDcPrui4CDwG3ufmpCFe3+Fot0\nXNEBRZm999PAwmq8/wjcAqwGXgV8tGxwk14fvTVt/P2XimG8TNmyVertwsCcKvHGaFuVz7aN9YYs\nu5TayW9mrwbe4u4PFU/d4+5HiyW8vglcVbduEYlvmp5/NfAdgGKJrifM7I3Fa2uBQ1PGVlnqHqcp\ni/VAIW5l3nPhfgqxe92Fx6Hrbev3a5rkN+AoQNHb3wR8w8weZrh2393ThycisWi5rgll23i2P5aS\nZ46XbNdo2Sr1hizbxm2W8vPScl0icpbWD+9t+zXtumIML66qDceiXdq+XYq1DPX8IplS8otkSskv\nkiklv0imlPwimVLyi2Sq9Zf6uvZz1rKmucxW5W/b/nk1tX1DXNZsaps1dQlWPb9IppT8IplS8otk\nqvXH/Kk1eczcl2m82qgvMy6HPB+gnl8kU0p+kUwp+UUypeQXyZSSXyRTSn6RTJW61Gdmq4DPFYtz\nXAHsZLjgxo+Bze5+xsy2AOuBU8Ct7n4wUsyNqjJvWxvosmD3pNpmE3t+M/sU8DWGa/IBbAM+6+6/\nDcwAG8xsHrgWWAVsBL4cJ1wRCaXMbv+zwHtHHl8NLCzAuQe4DngXsM/dB+7+HLDMzC4JGqmIBDUx\n+YuFN3858tRMMU8/wEngYobr8x0fKbPw/ESTdnEGg8FZt6bLjpcrW3bhceh6U39eC/dTxqBtVr7s\nUuoM7z0zcn8OOAacKO6PPz9RrnPAVxHrM6gTQ8h2jda7oC/brIpUQ4HrnO0/bGZrivvXA/uBA8A6\nM5s1s8uAWXf/eY26RaQhdXr+TwB3m9n5wJPAA+5+2sz2A48y/IeyOWCMIhKBluuaULYNu5Da7a9W\ntg3brIoGtpmW6xKRVyj5RTKl5BfJVK9n8ok1C2rqmVhD1dnU59OXIcZtWFY95Gernl8kU0p+kUwp\n+UUy1etj/hDHmtPU0fZj3SrxNbWKTNPGP4NY26yN3wX1/CKZUvKLZErJL5IpJb9IppT8IplS8otk\nqteX+lJenlr4eWhfda1tZeKt85PeEJ9Da2fvFZF+UvKLZErJL5KpXh/zpx5Smfr9Y+liu8rGPGk6\n7rK6cE6kznJdbwW+CJwGXgJ+z93/08y+APwWwzn7ATa4+/HFaxSR1CYmf7Fc143AC8VT24Fb3P1x\nM/sIcBvwB8A8sE5Tdot0Q53luja6++PF/WXAL8xsFngz8BdmdsDMNgWOU0QCKzV1t5ldDtzn7teM\nPPebwA5gNfAL4PcZLuJ5HvAQsMndn5hQdfcOHkU6pBi3EG7qbjN7P3AXsN7d/wt4Edju7i+6+0ng\nu8DKssFNen30FqqstEOM7TteLsV3Idb3tmrZpVQ+229mHwQ+Aqxx9/8pnl4B3Fcs1T3LcNXev6pa\nt4g0p1Lym9l5wBeA54BvmBnAw+6+xczuBR5juKLvX7v7P5etN9ZsuBreG17sdqX8LrRlmzX1HW/F\ncl191JYvUmh9bRfEbVuVZcgivLeW6xKRVyj5RTLViuG9bR4uWmWVlrrluqbt7WrDNptmV76pGNTz\ni2RKyS+SKSW/SKaU/CKZUvKLZKoVZ/uX0sYBJSEmg2xju8ro2yCf0bZ0oW0hJ/tUzy+SKSW/SKaU\n/CKZUvKLZKr1J/zGxRr6WOXEXNMzwcZS9+TRpHKpVqA51/svZTy2NgzvbYp6fpFMKflFMqXkF8mU\nkl8kU0p+kUzVWa5rHngQeLp4+U53v9/MtgDrgVPAre5+MErES2jqLHNfh/fGWsN+2veMadrhvW24\nalNXneW65oFt7r51pMw8cC2wCrgU2AW8PXi0IhJMneW6rgbWm9n3zWyHmc0xnKd/n7sP3P05YJmZ\nXRIhXhEJZGLyu/suhnPxLzgIfNLdVwNHgS3ARcDoirwngYvLBDBpt2kwGJx1a7rseLmyt0ltq1tv\n6tukdk27HWLGPen968QT4zMIWXYpdUb47Xb3Ywv3GS7X/U1gbqTMHHBs/A8XM+n4scpxfIyydY9J\nB4PuHfOXMaldMN12iKXMdlhoW+h6lyrXZNlxdZJ/r5ndUpzQWwscAg4Af2ZmdwBvBGbbvlT3pP+K\nVctV/dtp6g0l1vDeKm2L8TnEGt47Tb2hyoZUJ/k/BnzJzF4GngdudvcTZrYfeJThocTmgDGKSASt\nWK4rxS6R9PfzmubHWCnqnSaGMvkw0HJdIjJKyS+SKSW/SKY6N5lHKLrU9/+FGt7b9bY19X5LxdEE\n9fwimVLyi2RKyS+SKSW/SKayPeE3jRDDYLs8oKZq7KkHwlSJIVasbTxBqp5fJFNKfpFMKflFMqXk\nF8mUkl8kU50721/lzGjTZ1GbmhUmRJ2L1Vvy56FBP9emfrIda3hvl6/aqOcXyZSSXyRTSn6RTLX+\nmD/WMVXqWWNj1RGrXaMxtP04N9akqynqianOcl33Ab9WvHQ58Ji7bzSzbwGvYzjH//+6+/UxAhaR\nMCov1+XuG4vnXwM8BHy8KHoF8Bvu3v5/eSJSa7muBbcDX3T3/zCz1wOvBh40s0fM7HdCBiki4dVZ\nrgsz+1WGC3bsLJ46H9gK3MDwH8WfF2UmSnVsVHfZpapLPzUt1tJPsXQt3hi6tFwXwO8CX3f308Xj\n54G73P0U8DMzOwwY8LNJFYVc7rmKaebwq7L0U+qfs7Z9nYOuxRtDquW66l7quw7YM/b47wDM7FXA\nlcCTNesWkQbU7fmN4Qq9ALj7HjNbZ2aPAWeAT4daq6+NPUOIy2lNXWoMPRw69PDeaYSOoy1ta+y7\nketyXZq6u57YCZJyxpu2JH8VWq5LRCpT8otkqvXDe2NpYghoigk8mzhHkvKyYBltnMCzjdTzi2RK\nyS+SKSW/SKaU/CKZUvKLZErJL5Kpzl3qizV7b4hLPNPO3ttmsWbvHdf08O02brOmPgP1/CKZUvKL\nZErJL5Kpzh3zt3n45XhsbY61qliz96Y+xm7DNmtixuXFqOcXyZSSXyRTSn6RTCn5RTKl5BfJlJJf\nJFOtmMCzj9oyVDS0vrYL+ts2TeApImdJ3fOLSCLq+UUypeQXyZSSXyRTSn6RTCn5RTKl5BfJlJJf\nJFNJJvMws1ngK8BK4CXgJnd/JkUsoZjZYeB48fCnwFeB7cApYJ+7354qtjrMbBXwOXdfY2ZXADuB\nAfBjYLO7nzGzLcB6hm281d0PJgu4pLF2zQMPAk8XL9/p7vd3sV11pJrJ5wZgubu/08yuAbYCGxLF\nMjUzWw7g7mtGnnsceB9wFPi2mc27+4/SRFiNmX0KuBF4oXhqG/BZd/+emd0FbDCzfwGuBVYBlwK7\ngLeniLesRdo1D2xz960jZebpWLvqSrXb/y7gHwDc/THgbYniCGUlcKGZ7TOz75rZauACd3/W3QfA\nXmBt2hAreRZ478jjq4GHi/t7gOsYbsN97j5w9+eAZWZ2SbNhVrZYu9ab2ffNbIeZzdHNdtWSKvkv\n4pVdZIDTZta5+QRHvAjcAawDPgr8ZfHcgpPAxQniqsXddwG/HHlqpvgnBq+0ZXwbtr6Ni7TrIPBJ\nd1/NcA9tCx1sV12pkv8EMDcah7ufShRLCE8Bf1v0Fk8x/PK8duT1OeBYksjCODNyf6Et49uwi23c\n7e6HFu4DV9GPdpWSKvkPAO8BKI75jySKI5RNDM9bYGZvAC4EXjCzN5nZDMM9gv0J45vWYTNbU9y/\nnmFbDgDrzGzWzC5j+A/856kCrGmvmb2juL8WOEQ/2lVKql3t3cC7zewHwAzw4URxhLID2GlmjzA8\nI76JYW95L3Aew2PIHyaMb1qfAO42s/OBJ4EH3P20me0HHmXYiWxOGWBNHwO+ZGYvA88DN7v7iR60\nqxT9pFckUxrkI5IpJb9IppT8IplS8otkSskvkiklv0imlPwimfo/Qzp1aHauOqgAAAAASUVORK5C\nYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x2097c10d390>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    },
    {
     "data": {
      "text/plain": [
       "array([[  0,   0,   0, ...,   0,   0,   0],\n",
       "       [  0,   0,   0, ...,   0,   0,   0],\n",
       "       [255, 255, 255, ..., 255,   0,   0],\n",
       "       ..., \n",
       "       [  0,   0, 255, ..., 255, 255, 255],\n",
       "       [  0,   0,   0, ...,   0,   0,   0],\n",
       "       [  0,   0,   0, ...,   0,   0,   0]], dtype=uint8)"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "mazeGen_Prim()\n",
    "mazeGen_ReBT()\n",
    "mazeGen_ReD()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def standardize(im):\n",
    "    sim = np.roll(im, 1, axis=0)\n",
    "    mask = (sim == im).all(axis=1)\n",
    "    mask[0] = False\n",
    "    im = im[~mask]\n",
    "    \n",
    "    sim = np.roll(im, 1, axis=1)\n",
    "    mask = (sim == im).all(axis=0)\n",
    "    mask[0] = False\n",
    "    im = im[:,~mask]\n",
    "    return im"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def neiPairsOf(idim, trans=-1, shift=None):\n",
    "\n",
    "    shift = shift or (lambda im,pairs:[np.roll(im,(d,r),axis=(0,1)) for d,r in pairs])\n",
    "    \n",
    "    def toNeiPairs(a, b):\n",
    "        a = a.reshape(-1, 1)\n",
    "        b = b.reshape(-1, 1)\n",
    "        pairs = np.hstack([a,b])\n",
    "        pairs = pairs[pairs[:,0] != trans]\n",
    "        pairs = pairs[pairs[:,1] != trans]\n",
    "        return pairs\n",
    "    \n",
    "    neiPairs = [toNeiPairs(idim, neimage) for neimage in shift(idim, [(1,0),(0,1)])]\n",
    "        \n",
    "    return np.vstack(neiPairs)\n",
    "\n",
    "def to_id_image(im, transOld=0, transNew=-1):\n",
    "    idim = np.arange(im.ravel().shape[0]).reshape(im.shape)\n",
    "    idim[im==transOld] = transNew\n",
    "    return idim\n",
    "\n",
    "def toCoords(ids, shape):\n",
    "    ids = array(ids)\n",
    "    m,n = shape\n",
    "    r = ids // n\n",
    "    c = ids % n\n",
    "    return np.column_stack([r,c])\n",
    "\n",
    "def toIDs(coords, shape):\n",
    "    coords = array(coords)\n",
    "    m, n = shape\n",
    "    r, c = coords.T\n",
    "    if isinstance(r, np.ndarray):\n",
    "        r[r<0] += m\n",
    "        c[c<0] += n\n",
    "    else:\n",
    "        r = r if r>=0 else r + m\n",
    "        c = c if c>=0 else c + n\n",
    "        \n",
    "    return r * n + c\n",
    "\n",
    "def plotGroup(im, group):\n",
    "    plt.imshow(im)\n",
    "    \n",
    "    yx = toCoords(list(group), im.shape)\n",
    "    plot(yx[:,1],yx[:,0],'r.')\n",
    "    plt.axis(\"off\")\n",
    "    plt.show()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def shift_zeropadding(arr, disp_pairs):\n",
    "    h,w = arr.shape\n",
    "    paded = np.zeros((h+2,w+2), dtype=int)\n",
    "    paded[1:-1,1:-1] = arr\n",
    "    \n",
    "    shift = lambda d,r: paded[-d+1:-d+1+h, -r+1:-r+1+w]\n",
    "    return [shift(d,r) for d,r in disp_pairs]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from graph import graph"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 80,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAPkAAAD6CAYAAABj2+E+AAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAADq5JREFUeJzt3U1oVFcfx/HfzYRYnDiKC1eCOJrQ\nioGiYayg0Y2tLqS0CFVBBTdqLRqxkhCJSXHQRjd92WgXRbDaFqqLUpC+ROhoo0MpCjGI0i4KTaP4\nkkVmEHLj3GchnafmMZnMZO7Mvf/n+wGhk2nO/edkfvdM7pxzruN5nicAZtVUuwAA/iLkgHGEHDCO\nkAPGEXLAOEIOGFdbyjflcjl1d3frzp07qqurUzKZ1IIFC8pdG4AyKGkk/+mnnzQ6Oqqvv/5aBw8e\n1IcffljuugCUi1eCY8eOed99913+8apVqyb9/yV5/f39nqTQ/AtTvWGqNWz1hqnWiZT0dj2Tyai+\nvj7/OBKJaGxsTLW1L26uv79fS5cuVdgm14Wp3jDVKoWr3jDV+iIlhby+vl7ZbDb/OJfLTRhwSWpq\napLneXIcp5TDVUWY6g1TrVK46g1brS9S0t/ky5YtUyqVkiTdvHlTjY2NpVcGwFdOKQtU/rm6fvfu\nXXmep2PHjmnRokV+1BdaUzn7h/1tYCET9cG/R0frfeCn8f07UV+WFHIURsgJud+mGnImwwDGEXLA\nOEIOGEfIAeMIOWAcIQeMI+SAcYQcMI6QA8YRcsA4Qg4YV9JS02I5jlORJXulzIOeyvxqv5Sr/fG1\nlrMfgqiStVaqb/2cw89IDhhHyAHjCDlgHCEHjCPkgHGEHDCOkAPGEXLAuIpMhhkvbJv3Baneak1a\nKXcfTKc9v34fYZoQVAxGcsA4Qg4YR8gB4wg5YBwhB4wj5IBxhBwwjpADxhFywDhCDhhHyAHjCDlg\nXFUWqPi1ECBsCxeCtPClkHL2wb93QA3j7qd+8HNxDCM5YBwhB4yb9O2667rq6OjQ4OCgRkdHtWfP\nHi1evFjt7e1yHEcNDQ3q6upSTQ3nCiCoJg35t99+qzlz5ujkyZMaHh7WW2+9pZdfflmtra1asWKF\njhw5ot7eXq1bt65S9QIo0qRD8Pr167V///7840gkooGBASUSCUlSS0uL+vr6/K0QwLRMOpJHo1FJ\nUiaT0b59+9Ta2qqenp78lcBoNKqRkZGCB+nv75cUzCuek9UUpnqnW2ulf9Ygbv9kpW/HK/jH9NDQ\nkLZv364333xTGzdufO7v72w2q1gsVvAgTU1Nkp59TODnv1JM1lZY6h3/9XL2g18/t9+1lqvd8V/3\nq14/X0+Thvzhw4fauXOnDh06pE2bNkmSlixZonQ6LUlKpVJqbm4u6QcHUBmON8l7iWQyqUuXLike\nj+e/dvjwYSWTSbmuq3g8rmQyqUgkMvlBHCewEyAmajeo9fqlUL1hqlUq3++sHLcu9sv4eieqbdKQ\nl7OYoIaGkD9DyO2GnA+4AeMIOWAcIQeMI+SAcYQcMI6QA8YRcsA4Qg4YR8gB4wg5YBwhB4yrym6t\nKN1U5lcHhV/rAqopiP1cCCM5YBwhB4wj5IBxhBwwjpADxhFywDhCDhhHyAHjQjMZptIb6k/3mGG7\nAUAYJ3lUQ5Am70z1d8ZIDhhHyAHjCDlgHCEHjCPkgHGEHDCOkAPGEXLAOEIOGEfIAeMIOWAcIQeM\nq8oCFb8WQ5SyeMCvHUWn8jOWq91K7NYatgUsQaq32rUwkgPGTSnkjx490po1a/THH3/ozz//1JYt\nW7R161Z1dXUpl8v5XSOAaSgYctd1deTIEb300kuSpOPHj6u1tVXnz5+X53nq7e31vUgApSsY8p6e\nHm3evFnz5s2TJA0MDCiRSEiSWlpa1NfX52+FAKZl0gtvFy9e1Ny5c7V69Wp99tlnkp6/yBONRjUy\nMlLwIP39/fnvDRp2hqmOIPatX8er9u9m0pBfuHBBjuPo2rVrun37ttra2vT48eP889lsVrFYrOBB\nmpqaKnIFmKvr4VCJvi2X8X0b5Honqm3SkJ87dy7/39u2bVN3d7dOnjypdDqtFStWKJVK6bXXXitv\npQDKquiP0Nra2vTpp5/qnXfekeu6euONN/yoC0CZOF4F/mBwHCdUb3//aSuI9fqlUL1B6ls8M75/\nJ+pLJsMAxhFywDhCDhhHyAHjCDlgHCEHjCPkgHGEHDCOkAPGEXLAOEIOGEfIAeOqslsrninXOuOw\nrSefrmquJw8jRnLAOEIOGEfIAeMIOWAcIQeMI+SAcYQcMI7PyauonJsY/j9tiBi2mytUehPS8RjJ\nAeMIOWAcIQeMI+SAcYQcMI6QA8YRcsA4Qg4YR8gB4wg5YBwhB4wj5IBxphao+LXhXpA28ntRLeM3\nG/RzsUMQVHMjxzAuBGIkB4wj5IBxU3q7fvr0aV2+fFmu62rLli1KJBJqb2+X4zhqaGhQV1eXamo4\nXwBBVDCZ6XRaN27c0JdffqmzZ8/q3r17On78uFpbW3X+/Hl5nqfe3t5K1AqgBAVDfvXqVTU2Nmrv\n3r3avXu31q5dq4GBASUSCUlSS0uL+vr6fC8UQGkKvl0fHh7W33//rVOnTumvv/7Snj17nrviGI1G\nNTIyMmkb/f39kqZ3ZbIaVzWDeCV1opqmW2uYtlQKU63l+P7ptlsw5HPmzFE8HlddXZ3i8bhmzJih\ne/fu5Z/PZrOKxWKTttHU1PTciSEMH/FU4h5Y5eqHsH2EFqbXQqX6thztTtRGwbfry5cv15UrV+R5\nnu7fv68nT55o5cqVSqfTkqRUKqXm5uaiCwRQGY43hVPIiRMnlE6n5XmeDhw4oPnz56uzs1Ou6yoe\njyuZTCoSiUx8EMeZ9tk7bCq5Q2clRpsg/c786lu/VHskn1LIp4uQvxghLw0hf3G7Jb9dBxBuhBww\njpADxhFywDhCDhhHyAHjCDlgHCEHjCPkgHGEHDCOkAPGVWW3Vr+WCpZzznYl5tr/v+6QWollvOVq\nvxK1+o2RHDCOkAPGEXLAOEIOGEfIAeMIOWAcIQeMI+SAcVWZDBP0vbbLIWwTaMJ2w4JKClOtL8JI\nDhhHyAHjCDlgHCEHjCPkgHGEHDCOkAPGEXLAOEIOGEfIAeMIOWAcIQeMq8oCFb/4tXgjbItCgr6Y\nZ7o74Vby5xu/W6tf9fq5CIaRHDCu4Ejuuq7a29s1ODiompoaHT16VLW1tWpvb5fjOGpoaFBXV5dq\najhfAEFUMOQ///yzxsbG9NVXX+mXX37RRx99JNd11draqhUrVujIkSPq7e3VunXrKlEvgCIVHH4X\nLlyop0+fKpfLKZPJqLa2VgMDA0okEpKklpYW9fX1+V4ogNIUHMlnzpypwcFBbdiwQcPDwzp16pR+\n/fXX/MWEaDSqkZGRSdvo7++XNL2LC9XYnSOIO4JMVFMQa51MmF4L0z2eX/VOtd2CIT9z5oxWrVql\ngwcPamhoSDt27JDruvnns9msYrHYpG00NTWF6oqqVJl7YJWrH8J2v64wvRaCfHV9fLsTtVHw7Xos\nFtOsWbMkSbNnz9bY2JiWLFmidDotSUqlUmpubi66QACV4XgFTiHZbFYdHR168OCBXNfV9u3btXTp\nUnV2dsp1XcXjcSWTSUUikYkP4jihOntLjOR+CtNrwcJIXjDk5VCOkIdNtSdABIFft4UOW99WO+R8\nuA0YR8gB4wg5YBwhB4wj5IBxhBwwjpADxhFywDhCDhhHyAHjCDlgHCEHjAvNbq3VXIUW9F1VK7VS\nKkyC1LfVxkgOGEfIAeMIOWAcIQeMI+SAcYQcMI6QA8YRcsC40EyGmYpyT1TgLh/Twy2f/TXVfmAk\nB4wj5IBxhBwwjpADxhFywDhCDhhHyAHjCDlgHCEHjCPkgHGEHDCOkAPGVWWBil8LAcrZ7vhdOoMs\nTLWOF7a6g/zanWjBCiM5YBwhB4wj5IBxjhfGW0IAmDJGcsA4Qg4YR8gB4wg5YBwhB4wj5IBxvk9r\nzeVy6u7u1p07d1RXV6dkMqkFCxb4fdiiuK6rjo4ODQ4OanR0VHv27NHixYvV3t4ux3HU0NCgrq4u\n1dQE55z46NEjvf322/r8889VW1sb6FpPnz6ty5cvy3VdbdmyRYlEIpD1uq6r9vZ2DQ4OqqamRkeP\nHg18306J57Pvv//ea2tr8zzP827cuOHt3r3b70MW7ZtvvvGSyaTneZ73+PFjb82aNd6uXbu869ev\ne57neZ2dnd4PP/xQzRKfMzo66r377rve66+/7v3++++BrvX69everl27vKdPn3qZTMb75JNPAlvv\njz/+6O3bt8/zPM+7evWq99577wW21mL4fkr67bfftHr1aknSq6++qlu3bvl9yKKtX79e+/fvzz+O\nRCIaGBhQIpGQJLW0tKivr69a5f2Pnp4ebd68WfPmzZOkQNd69epVNTY2au/evdq9e7fWrl0b2HoX\nLlyop0+fKpfLKZPJqLa2NrC1FsP3kGcyGdXX1+cfRyIRjY2N+X3YokSjUdXX1yuTyWjfvn1qbW19\nbmVXNBrVyMhIlat85uLFi5o7d27+xCkpsLVK0vDwsG7duqWPP/5YH3zwgd5///3A1jtz5kwNDg5q\nw4YN6uzs1LZt2wJbazF8/5u8vr5e2Ww2/ziXy6m2Nni3YBsaGtLevXu1detWbdy4USdPnsw/l81m\nFYvFqljdf124cEGO4+jatWu6ffu22tra9Pjx4/zzQapVkubMmaN4PK66ujrF43HNmDFD9+7dyz8f\npHrPnDmjVatW6eDBgxoaGtKOHTvkum7++SDVWgzfR/Jly5YplUpJkm7evKnGxka/D1m0hw8faufO\nnTp06JA2bdokSVqyZInS6bQkKZVKqbm5uZol5p07d05ffPGFzp49q1deeUU9PT1qaWkJZK2StHz5\ncl25ckWe5+n+/ft68uSJVq5cGch6Y7GYZs2aJUmaPXu2xsbGAvs6KIbvC1T+ubp+9+5deZ6nY8eO\nadGiRX4esmjJZFKXLl1SPB7Pf+3w4cNKJpNyXVfxeFzJZFKRSKSKVf6vbdu2qbu7WzU1Ners7Axs\nrSdOnFA6nZbneTpw4IDmz58fyHqz2aw6Ojr04MEDua6r7du3a+nSpYGstRisQgOMC9kHfgCKRcgB\n4wg5YBwhB4wj5IBxhBwwjpADxhFywLj/AP1lHh3YBR7uAAAAAElFTkSuQmCC\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1a334ff3908>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "mazeGen = mazeGen_BrkCir\n",
    "maze = mazeGen(10,10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 81,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAQIAAAD3CAYAAAD2Z1pOAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAABCRJREFUeJzt3UFu01AYRtFbSiXW0L2wevbSNSBV\nKIwYILXCoXGff+ecYYWI7VZXb/DJebhcLpeAu/Zl9QUA6wkBIASAEAAJAVB9XX0Bfzw+Pa++BDi9\nX68vb/7ciQAQAkAIgIQASAiAhABICICEAEgIgA60LPz58mP1JSzx7fn75n97tme09d7Pdt97uObv\n6C1OBIAQAEIAJARAQgAkBEBCACQEQEIAJARAB5oYf3Qi+RHXTFhXXuetP3vKfW91tr+hz5xWOxEA\nQgAIAZAQAAkBkBAACQGQEAAJAdCBloVbTXmR5crrnLKwm/DZExaVt+BEAAgBIARAQgAkBEBCACQE\nQEIAJARAQgA0cGK8x+RzyjR1wrx65X1f89n3+izf40QACAEgBEBCACQEQEIAJARAQgAkBEADl4VT\nvsp7jzXcrT97DxMWe6sdccnqRAAIASAEQEIAJARAQgAkBEBCACQEQAOXhfzblK/y3nqdE9aKU575\ne5wIACEAhABICICEAEgIgIQASAiAhABICIBOPjHeY5p66/9zwjXW/Ant3lbPoL28FPgwIQCEABAC\nICEAEgIgIQASAiAhABq4LFz9NeK3fuHmNfez8qvWt5qyQPSM/uZEAAgBIARAQgAkBEBCACQEQEIA\nJARAA5eFe6wAz2blOwtX/n5WvzdwqyO+U9KJABACQAiAhABICICEAEgIgIQASAiAhABo4MT4nt3r\nZHorz+f/OREAQgAIAZAQAAkBkBAACQGQEAAJAZBl4ShTXs65ypTnc8QXwToRAEIACAGQEAAJAZAQ\nAAkBkBAACQGQEACZGFf7vPRy5Ys0jzhh/Qwrr3HKvPk9TgSAEABCACQEQEIAJARAQgAkBEBCAHTy\nZeGEtdeExd41JjzzmnOdn8WJABACQAiAhABICICEAEgIgIQASAiABi4L91ji7fHuvj2WaxNWiBOu\nseZc52dxIgCEABACICEAEgIgIQASAiAhABICICEAGjgxPttXeU+ZInvZ57k5EQBCAAgBkBAACQGQ\nEAAJAZAQAAkB0MBl4R72WOJNWPdNWF7W9vteeT9TXoD7HicCQAgAIQASAiAhABICICEAEgIgIQA6\n+bJwwnv2JiwQ9zJlCXgPnAgAIQCEAEgIgIQASAiAhABICICEAEgIgE4+MT7bhPXW93O2r5i/xspn\neUROBIAQAEIAJARAQgAkBEBCACQEQEIAdPJl4VYrV2FTFmlnW0puNWVR+dF7dyIAhAAQAiAhABIC\nICEAEgIgIQASAiAhAKqHy+VyWX0RVY9Pz6svAU7v1+vLmz93IgCEABACICEAEgIgIQASAiAhABIC\noAMtC4F1nAgAIQCEAEgIgIQASAiAhABICICEAEgIgIQASAiAhABICICEAEgIgIQASAiAhABICICE\nAEgIgOo3B/zPJem/xGIAAAAASUVORK5CYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x1a334ec5f60>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "stdmaze = standardize(maze)\n",
    "idim = to_id_image(stdmaze)\n",
    "nepairs = neiPairsOf(idim, shift=shift_zeropadding)\n",
    "way = graph(nepairs).serch(toIDs((1,0), stdmaze.shape), toIDs((-2,-1), stdmaze.shape))\n",
    "plotGroup(stdmaze, way)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 82,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "4"
      ]
     },
     "execution_count": 82,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "len(graph(nepairs).equivalence)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 232,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(100, 100)"
      ]
     },
     "execution_count": 232,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "maze.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 78,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "plt.imsave(\"maze_rebt_80.png\", maze)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(-0.5, 60.5, 60.5, -0.5)"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAAP0AAAD5CAYAAADspDPqAAAABHNCSVQICAgIfAhkiAAAAAlwSFlz\nAAALEgAACxIB0t1+/AAAADl0RVh0U29mdHdhcmUAbWF0cGxvdGxpYiB2ZXJzaW9uIDIuMS4wLCBo\ndHRwOi8vbWF0cGxvdGxpYi5vcmcvpW3flQAACIBJREFUeJzt3dtyqzgQBdB4av7/lz2vGVcFg6Cl\nhr3W26kTc4t3SZ1G8Hq/3z9Ajn9WHwAwl9BDGKGHMEIPYYQewgg9hBF6CPPvjJ28Xi83A0Cx9/v9\n2vNzRnoII/QQRughzJSafuv+/tfr/2XI75/d+r9vfn/283Oj/5fgzDXv5CnnseXzHPcy0kMYoYcw\ns1p2//v3FVOtFdO30elUd3uv3VPOf8Z5bJWNqxnpIYzQQxihhzBTavo7OfK3gb3txarW42yjrddv\nKs7xSA1d0Qo+so/R746WHbCL0EMY0/sPM6bTo9PAI9vZ2uaRqfhVU9a9nzuynSozyo2VpZqRHsII\nPYQReggTWdPPrqdGa99V2927j5GfO/rZ0e12uu21GyM9hBF6CBM5vZ99l9tV7ZqK9tlV++c+jPQQ\nRughjNBDmMfW9BW1+optju6zosZfvcrvqWZfVyM9hBF6CCP0EOaxNf3q5ZFbdfNVNfWM/vudevNX\nPFVmhdnLbo30EEboIcxjp/erzXjAY3oLbfVtyXdlpIcwQg9hhB7CqOlPGG11jb4Io6oWrWh1jbYX\nz7QlK/7+8cT630gPYYQewpjeH1D1LrfRfc4w4zy6tSU7HWvFNo30EEboIYzQQ5iImn607XKmXXOn\nW0RnH0+387/qGI6s7Ny7j4rrYaSHMEIPYSKm90faHlfduVXxQMsVZhzP7HM+MmWuenDJ6F2QV9w9\naaSHMEIPYYQewkTU9KsfRHnVSrEVuh0P5xnpIYzQQxihhzDLa/qtHm3Vss6t2yVn9Ey79eLTfPtd\nzfhO7mVpLXCa0EOY5dP7rdtXZ7/ja5bZbbBvJczea37n9t2R787e8m/G97EiA0Z6CCP0EEboIczy\nmn6F2cten/K3iE9X1ckJOp2zkR7CCD2EWTK9H30HXMUqt9Ep6pHPdm+DdbuuW7pdu706tZ+N9BBG\n6CGM0EOYJTX97Fq4U7vkU7djq7que392xZOL0xjpIYzQQ5jld+TNaGVUvVN8xTvy/lL1UoYtR67r\njHe3dWrnVe3/iu0a6SGM0EMYoYcwy2v6LVc9oPCqn73qveqdXwo54zxWn/+Mer/qoa6/eYElsIvQ\nQxihhzCta/qrnpQ72k8+0/uuWCK8papPP3up81NVLMseZaSHMEIPYVpP76+yon2yevXc6v13llhe\n/GakhzBCD2GEHsJE1PSfZizzTK8b76Ti6czffv+zW7q/GekhjNBDmMjpvXZWtm7t1dmM9BBG6CGM\n0EOYiJo+vX224km53VSswrwrIz2EEXoIEzG9T2vJfHOn6zGjvTbj/XkVPBgT2EXoIYzQQ5jXjBrl\n9Xrt3kmnlxCmcM2f4f1+7/rlGekhjNBDGKGHMEv69KM15JGXXWy9tIK/dbtWnV4ScUbFeejTA7sI\nPYSJuA232yqqbi2ybsez11XvFqxwpJyYfWxGeggj9BBG6CFMRE1/1dLJijbQmW1UtCVXt7aOuNOx\nHlH9NxYjPYQReggTMb0fnSJ9mz52am91Opafn2c+UPLTXc/RSA9hhB7CCD2Eiajpq1o7T20ZVRi9\nVt1Wy20ZfaHGbEZ6CCP0EEboIUxETV9VT61ertmpTpwl8ZyvZqSHMEIPYSKm953bPGfsbRHd+fwr\nWnYrHqraqSwx0kMYoYcwQg9hImr6TvXUNzPacp2vx5mnyM54qu/e7Xb+O4qRHsIIPYSJmN7f+T13\nV61Ou2KbVSqm4jPOsdt13MtID2GEHsIIPYSJqOmP2Kr3O7e6tpw57tkvt/y2j63/r3rq8V53+X4Y\n6SGM0EOYyOn96HTuTi2ap7znbsYquwqdS0MjPYQReggj9BAmoqYfrac61WE/P9fVid3O64jVbbkn\nMNJDGKGHMEIPYSJq+jsvrd0y+sLE1f32qqfj7N3uivPf2ufs4zHSQxihhzAR0/st3dpX3R6MWbHK\nbkbpUVEWPOV4jPQQRughjNBDmOU1/eqW2er9f1PxNNzRfZy5VqMtu06trm8qjqdim0Z6CCP0EGbJ\n9L7b3WK/dWvhXeHMwyZHnbnrbrbRh22e+R7vPeeKdp6RHsIIPYQRegizpKbfe2tnt9VQd1KxkvBM\nfTnaequoaY/U21Xfh5XfMyM9hBF6CLP8jrwtHVZDjdq7iqrD++FGj+dIabZ3u91afTMexGmVHVBK\n6CGM0EOY5TV9t7Zct/bRbDOO584v1HwCIz2EEXoII/QQZnlN37nXWrXd1UtJVztz/jOWAa/+To7+\n315Geggj9BBm+fR+xvvYOqwy66TbeXR7t+DsYxh9EcboVN9ID2GEHsIIPYS51dNwr6rxZ7yIcbYz\nbafZ59Ft+ewKnpwDTCP0EGb5gzFHf67iCTffVLS6qtpns1cLftOt/Trb6Pl7lx1wmtBDGKGHMMtv\nw+38pNirXkJ4ZLsVT5j95orzuGrl3IxrXvX3oLusujTSQxihhzDLp/dbqlp2nR7MeGYbo59d/X64\nyv2s3GbF3aRW2QGnCT2EEXoI07qm79SSunK7R/a5um25ZXZ79cx+ZtzSvXd/3/bvBZbApYQewgg9\nhGld038arSE79eXvsM+/XLU89og7vVDzLoz0EEboIcytpvejrmrzVNxK2uHBj1ccz7e2096VdCuu\nx4rvx8rfu5Eewgg9hBF6CNO6pu/ealu9tHbUitbbXqv3f0bFEllPwwVOE3oI03p6v3qV3art/qXb\ngzFHt3mX1lYHFSvwjPQQRughjNBDmNY1/VW3a965DbSl09Nwq3Q+tiMq2nKjnzPSQxihhzCvSe8m\nf8YcDRp7v9+7al4jPYQReggj9BBmSk0P9GGkhzBCD2GEHsIIPYQReggj9BBG6CGM0EMYoYcwQg9h\nhB7CCD2EEXoII/QQRughjNBDGKGHMEIPYYQewgg9hBF6CCP0EOY/qlVbd9ulR8MAAAAASUVORK5C\nYII=\n",
      "text/plain": [
       "<matplotlib.figure.Figure at 0x2097c830518>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "plt.imshow(stdmaze, cmap = cm.Greys_r, interpolation='none')\n",
    "plt.axis(\"off\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1801, 2)"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nepairs.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 97,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "am80 = plt.imread(r\"C:\\Users\\momos\\Desktop\\am80.png\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 98,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(545, 1040, 4)"
      ]
     },
     "execution_count": 98,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "am80.shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 121,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "mask = am80[:,:,-1]!=0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 122,
   "metadata": {},
   "outputs": [
    {
     "ename": "TypeError",
     "evalue": "reshape() takes exactly 1 argument (0 given)",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m                                 Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-122-843d04fc4458>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[1;32m----> 1\u001b[1;33m \u001b[0mam80\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mmask\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mreshape\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m",
      "\u001b[1;31mTypeError\u001b[0m: reshape() takes exactly 1 argument (0 given)"
     ]
    }
   ],
   "source": [
    "am80[mask].reshape()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 123,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def standardizepng(im):\n",
    "    mask = (im[:,:,-1]==0).all(axis=1)\n",
    "    im = im[~mask]\n",
    "    \n",
    "    mask = (im[:,:,-1]==0).all(axis=0)\n",
    "    im = im[:,~mask]\n",
    "#     sim = np.roll(im, 1, axis=0)\n",
    "#     mask = (sim == im).all(axis=1)\n",
    "#     mask[0] = False\n",
    "#     im = im[~mask]\n",
    "    \n",
    "#     sim = np.roll(im, 1, axis=1)\n",
    "#     mask = (sim == im).all(axis=0)\n",
    "#     mask[0] = False\n",
    "#     im = im[:,~mask]\n",
    "    return im"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 124,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(545, 1040, 4)"
      ]
     },
     "execution_count": 124,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "standardize(am80).shape"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 227,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "a = array([0,1,0,1, 0,0,0,1, 0,0,0,1, 0,0,0,0]).reshape(4,4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 228,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0, 1, 0, 1],\n",
       "       [0, 0, 0, 1],\n",
       "       [0, 0, 0, 1],\n",
       "       [0, 0, 0, 0]])"
      ]
     },
     "execution_count": 228,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 200,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0, 0, 0, 1],\n",
       "       [0, 0, 1, 0],\n",
       "       [0, 1, 0, 0],\n",
       "       [1, 0, 0, 0]])"
      ]
     },
     "execution_count": 200,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a@a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 201,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[0, 0, 1, 0],\n",
       "       [1, 0, 0, 0],\n",
       "       [0, 0, 0, 1],\n",
       "       [0, 1, 0, 0]])"
      ]
     },
     "execution_count": 201,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a@a@a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 202,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[1, 0, 0, 0],\n",
       "       [0, 1, 0, 0],\n",
       "       [0, 0, 1, 0],\n",
       "       [0, 0, 0, 1]])"
      ]
     },
     "execution_count": 202,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a@a@a@a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 209,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from scipy.sparse.csgraph import floyd_warshall"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 218,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([[  0.,   1.,  inf,   1.],\n",
       "       [  1.,   0.,  inf,   1.],\n",
       "       [ inf,  inf,   0.,  inf],\n",
       "       [  1.,   1.,  inf,   0.]])"
      ]
     },
     "execution_count": 218,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "floyd_warshall(a, directed=False, unweighted=True)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 221,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 221,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.isinf(_218).any()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 223,
   "metadata": {},
   "outputs": [],
   "source": [
    "def isconnected(arr):\n",
    "    dist = floyd_warshall(arr, directed=False, unweighted=True)\n",
    "    return not np.isinf(dist).any()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 231,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 231,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isconnected(a)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  },
  "toc": {
   "colors": {
    "hover_highlight": "#DAA520",
    "navigate_num": "#000000",
    "navigate_text": "#333333",
    "running_highlight": "#FF0000",
    "selected_highlight": "#FFD700",
    "sidebar_border": "#EEEEEE",
    "wrapper_background": "#FFFFFF"
   },
   "moveMenuLeft": true,
   "nav_menu": {
    "height": "11px",
    "width": "251px"
   },
   "navigate_menu": true,
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "threshold": 4,
   "toc_cell": false,
   "toc_section_display": "block",
   "toc_window_display": false,
   "widenNotebook": false
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
